Your friend X is a master of pranks and has been scheming his magnum opus prank: a prank so elaborate that it requires an entire team of accomplices. However, to maintain secrecy, X has imposed a strict condition:
- No two recruited accomplices can be friends with each other.
This way, if one of them is caught, they cannot directly expose any of the others.
You have been tasked with analyzing all possible ways to recruit a group of accomplices while ensuring this condition is met. Specifically, X wants to know how many distinct ways there are to form such groups of different sizes.
You are given a set of $$$n$$$ candidates numbered $$$1$$$ through $$$n$$$, along with a list of friendships between them. Each friendship is bidirectional—if candidate $$$a$$$ is friends with candidate $$$b$$$, then candidate $$$b$$$ is also friends with candidate $$$a$$$.
Your job is to determine, for each possible group size from $$$0$$$ to $$$n$$$, the number of ways to form such a group while satisfying X's constraint.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 40$$$, $$$0 \leq m \leq \frac{n(n-1)}{2})$$$—the number of candidates and the number of friendships.
Each of the next $$$m$$$ lines contains two integers $$$a$$$ and $$$ b $$$ $$$(1 \leq a, b \leq n$$$, $$$ a \neq b)$$$, indicating that candidates $$$a$$$ and $$$b$$$ are friends. There are no duplicate friendships.
Print $$$n+1$$$ integers on a single line, where the $$$i$$$-th integer represents the number of ways to form a valid group of exactly $$$i-1$$$ accomplices.
5 3 1 2 2 3 4 5
1 5 7 2 0 0
A=B's Header Image from its Steam store page After hours of playing the hit puzzle game A=B, you've become an expert at transforming strings using substitution rules. In A=B, players are challenged to manipulate strings using a minimalistic programming language that consists solely of substitution instructions of the form 'A=B'. Each instruction replaces occurrences of string 'A' with string 'B', allowing players to solve various problems—from simple character replacements to more complex transformations like multiplying binary numbers. Inspired by the game's elegant simplicity and the power of its single operation, you had an epiphany: "I could totally make this myself!"
With newfound inspiration, you decide to build your own version of the A=B interpreter. Your version will follow a strict sequence of substitution rules, carefully applying them one at a time until the string can't change any further—or until it grows out of control! You decide to include safety limits for memory and time, so your interpreter won't run away in an endless loop.
A=B's interpreter works as follows: first, it reads a starting string, as well as an ordered list of rules to apply. Each rule is a string of the form '$$$A$$$=$$$B$$$', where $$$A$$$ and $$$B$$$ are strings of uppercase letters without spaces. They each have at most $$$255$$$ characters. Note that $$$B$$$ may be empty.
One step of your interpreter consists of finding the first rule, $$$A$$$=$$$B$$$, such that the string $$$A$$$ occurs in the current string. Then your interpreter should replace the earliest occurrence of $$$A$$$ with $$$B$$$ in the current string.
If your interpreter does not find any rule that can be applied, then it should exit and output the current string.
If, after $$$5\,000$$$ steps, it is still possible to apply some rule, then your interpreter should output "Time Limit Exceeded" and exit immediately.
If at any point the length of the current string exceeds $$$255$$$ characters, your interpreter should immediately output "Memory Limit Exceeded" and exit immediately.
The first line contains the starting string $$$s$$$ ($$$1 \leq |s| \leq 255$$$).
The second line contains an integer $$$n$$$ ($$$1 \leq n \leq 20$$$), the number of substitution rules.
The next $$$n$$$ lines each contain a substitution rule of the form '$$$A$$$=$$$B$$$' ($$$1 \leq |A| \leq 255, 0 \leq |B| \leq 255$$$), where $$$A$$$ and $$$B$$$ are strings containing only uppercase English letters.
Print "Time Limit Exceeded" if the interpreter could perform more than $$$5\,000$$$ transformations.
Print "Memory Limit Exceeded" if the string length exceeds $$$255$$$ characters at any point.
Otherwise, print the value of the final string.
CBACAB 3 BA=AB CA=AC CB=BC
AABBCC
A 1 A=AA
Memory Limit Exceeded
AB 2 AB=C C=AB
Time Limit Exceeded
This year, Blaster wants to make a grand exit from graduation, and what better way to do so than by launching himself out of a cannon? Blaster's stunt can be modeled as a path in the XY-plane where the cannon is positioned at the origin, $$$(0, 0)$$$, and can be aimed at any angle.
Suspended in the air are $$$n$$$ floating hoops, each represented as a vertical segment. The $$$i$$$-th hoop is located $$$x_i$$$ meters along the X-axis. The bottom of the hoop is positioned $$$a_i$$$ meters above the X-axis, and the top of the hoop is positioned $$$b_i$$$ meters above the X-axis.
Blaster, modeled as a single point, will follow a perfectly straight-line trajectory after launch (since he has conveniently disabled Earth's gravity for this stunt). He is considered to pass through a hoop if his trajectory intersects or touches at least one point on the vertical line segment between $$$(x_i, a_i)$$$ and $$$(x_i, b_i)$$$ (inclusive).
Your task is to determine the maximum number of hoops Blaster can pass through if you carefully choose the cannon's launch angle.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of hoops.
Each of the next $$$n$$$ lines contains three integers $$$x_i, a_i, b_i$$$ $$$(1 \leq x_i \leq 10^9, 0 \leq a_i \leq b_i \leq 10^9)$$$, describing the position and height range of the $$$i$$$-th hoop.
Print a single integer—the maximum number of hoops Blaster can pass through for an optimal choice of launch angle.
5 2 1 3 4 2 5 3 1 4 5 3 6 1 2 3
4
Dr. Mehta, a professor of the Algorithms course at Colorado School of Mines, has recently observed an increase in students using generative AI to do their homework for them. He noticed that reports generated by AI tend to use certain words more than usual, especially the word "certainly". Dr. Mehta wants your help spotting dubious submissions!
Given a student's report, count the number of times the word "certainly" appears.
The input consists of a single line containing a string $$$s$$$ ($$$10 \leq |s| \leq 10^{4}$$$), consisting only of lowercase English letters, spaces (' '), and periods ('.').
Print one integer, the number of times the word "certainly" appears in $$$s$$$.
certainly. i can help you with that.
1
hello world
0
certainlycertainlycertainlycertainly
4
Colorado School of Mines has a big problem! Somebody left a piece of cheese in front of the Student Center, and now several students are infected with the "cheese touch". These infected students can spread it to anyone adjacent to them, but not through walls. Although a cure is being developed, it may not come fast enough to stop the spread.
The "cheese touch" spreads every $$$p$$$ minutes (at times $$$p, 2p, 3p, \ldots$$$), infecting people directly adjacent to infected individuals. The cure will be ready after $$$t$$$ minutes. The cure acts immediately, so the infection is not spread at time $$$t$$$ or any time after.
The first line of input contains two integers $$$p$$$ ($$$1 \leq p \leq 10^5$$$) and $$$t$$$ ($$$1 \leq t \leq 10^5$$$) representing the minutes it takes for the "cheese touch" to spread and the minutes it takes to find a cure, respectively.
The second line contains a single string $$$s$$$ ($$$1 \leq |s| \leq 10^3$$$) consisting of the characters 'H', 'I', and 'W' representing the initial configuration of Healthy people, Infected people, and Walls, respectively. It is guaranteed that there will be at least $$$1$$$ healthy person.
Print out "CURED" if the cure was released before all the healthy people became infected or "ALL INFECTED" if the cure came too late (without quotes).
1 3 HIH
ALL INFECTED
1 10 HWIIHI
CURED
2 4 HHIWHI
CURED
The 2024 Mines freshman class photo. Photo from Mines Nest. Retrieved from Instagram Every year, the Mines freshman class assembles on the football field to take a class photo. Usually, the students arrange themselves to create a giant M. Unfortunately, the students took too long to set up, causing Blaster to get hungry and eat the ropes outlining the M. Thinking quickly, the teachers assemble the students in a rectangle. Given that this rectangle is $$$w$$$ people by $$$l$$$ people, how many students are in the freshman class?
The first line of input contains a single integer $$$w$$$ ($$$1 \leq w \leq 10^4$$$), the width of the rectangle.
The second line of input contains a single integer $$$l$$$ ($$$1 \leq l \leq 10^4$$$), the length of the rectangle.
The only line of output should be a single integer, the total number of students in the freshman class.
50 110
5500
200 20
4000
When Blaster first started at Mines, he joined as many different extracurricular clubs as he could. He loves getting involved on campus, and he also loves that many clubs provide free pizza! Unfortunately, now he is in too many clubs, and some of the meetings overlap. Additionally, if he eats too much pizza, then he will be too full to do any more activities.
Blaster still wants to attend as many clubs as he can. Each club meeting is only one hour long, but some club meetings might be at the same time as each other. Different clubs give different amounts of pizza, so he needs to decide which meetings to go to in order to maximize the amount of clubs he goes to before getting full of pizza.
If Blaster chooses optimally, how many clubs will he be able to attend?
The first line of the input consists of two integers $$$n,c$$$ ($$$1 \leq n \leq 10^3, 0 \leq c \leq 10^6$$$)—the number of clubs and the number of pizza slices Blaster can eat before being full, respectively.
The $$$i$$$-th line of the following $$$n$$$ lines contains two integers $$$t_i, p_i$$$ ($$$0 \leq t_i \lt 24, 0 \leq p_i \leq 10^6$$$)—the hour of the day that the $$$i$$$-th club meets at and the number of pizza slices he will eat at the $$$i$$$-th meeting, respectively.
Output a single integer, the number of clubs that Blaster can attend.
3 6 18 3 19 2 20 1
3
3 3 18 3 19 2 20 1
2
8 100 4 4 19 26 13 89 6 50 0 96 19 32 6 31 23 76
3
In sample input 1, there are three clubs at 18:00, 19:00, and 20:00 that give $$$3$$$, $$$2$$$, and $$$1$$$ slices of pizza, respectively. Blaster can eat $$$6$$$ slices of pizza, so he can attend all three clubs.
In sample input 3, Blaster can either visit clubs $$$1$$$ and $$$3$$$ or visit clubs $$$2$$$ and $$$3$$$.
It is well known that Mines students have problems with adding. The complex algorithms they learn crowd out basic arithmetic operations. Thus, the Mines professors asked you to automate the calculation and assignment of final letter grades in order to stop the teaching assistants from messing up everyone's grades! Given a student's two midterm exam grades $$$x$$$ and $$$y$$$, as well as their final exam grade $$$z$$$, calculate their final letter grade for the class. Midterm exams are worth $$$25$$$% of the final grade each, and the final exam is worth the remaining $$$50$$$%. Note that no plus or minus grades are given, so all scores [$$$90\%$$$, $$$100\%$$$] get A's, all scores [$$$80\%$$$, $$$90\%$$$) get B's, all scores [$$$70\%$$$, $$$80\%$$$) get C's, all scores [$$$60\%$$$, $$$70\%$$$) get D's, and all scores [$$$0\%$$$, $$$60\%$$$) get F's.
The input consists of a single line containing three integers, $$$x$$$, $$$y$$$, and $$$z$$$ $$$(0 \leq x,y,z \leq 100)$$$—the student's grades on the first midterm, second midterm, and final exam, respectively.
The first and only line of output should contain a single character, the letter grade achieved by the student.
87 93 90
A
91 78 56
C
Graphic from visitgolden The city of Golden has many landmarks worth visiting. Before arriving in Golden, you made a list of landmarks you want to visit and the order in which you will visit them. To understand where these landmarks are located, you create a map of Golden and mark each landmark on it. You determine the $$$x$$$ and $$$y$$$ coordinates of each landmark and plot out your journey for the day. Now, you want to determine the total walking distance required to visit all landmarks in the given order. You will start at the first landmark and finish your walk at the last landmark. Since Golden is laid out on a grid, the walking distance between two landmarks at coordinates $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$.
The first line of input contains an integer $$$n$$$ ($$$ 2 \leq n \leq 10^5 $$$) representing the number of landmarks.
The next $$$n$$$ lines each contain a string $$$ s $$$ ($$$ 1 \leq |s| \leq 25 $$$), the name of a landmark, followed by two integers $$$x$$$ and $$$y$$$ ($$$ -10^4 \leq x, y \leq 10^4 $$$) representing the landmark's coordinates. Each landmark name consists only of uppercase and lowercase Latin letters and is unique.
The final line contains a space-separated sequence of $$$n$$$ landmark names, specifying the exact order in which you will visit them. Each landmark appears exactly once in this sequence.
Output a single integer, the total walking distance required to visit all landmarks in the specified order.
2 CTLM 1 1 MinesMarket 2 2 MinesMarket CTLM
2
5 ClearCreek 0 0 MinesM 20 10 SouthTable -20 -10 WoodysPizza 10 10 ColoradoSchoolOfMines 20 -10 ColoradoSchoolOfMines ClearCreek WoodysPizza SouthTable MinesM
160
Hill Climb Racing is a 2D mobile game where you drive speeding cars over hilly terrain while avoiding injuring the driver or running out of gas. An $$$l$$$ meter long track can be modeled as a 0-indexed array $$$h$$$ of $$$l+1$$$ integers where $$$h_i$$$ is the height in pixels at the $$$i$$$-th meter of the track. If the track becomes too steep for the car's acceleration, the car gets stuck on the hill and either flips over or runs out of gas.
Several of Mines' Computer Science undergraduates have been feeling nostalgic and recently began playing Hill Climb Racing again. However, they kept getting stuck on the steep hills in some tracks. Instead of upgrading their vehicles, the undergrads have decided to file bug reports for each track that they can't get over with their vehicles. After sifting through the game's code, they determined that a vehicle with acceleration value $$$a$$$ can ascend at most $$$a$$$ pixels per meter in the track. Note that a vehicle may descend any number of pixels per meter, no matter its acceleration.
Your job is to write a program which, given a track, determines if it can be climbed by a vehicle with acceleration $$$a$$$.
The first line of input consists of 2 integers, $$$l$$$ and $$$a$$$ ($$$1 \leq l, a \leq 10^6$$$)—the length in meters of the track and the acceleration value of the vehicle, respectively.
The second line of input contains $$$l + 1$$$ space separated integers, $$$h_0, h_1, \ldots, h_l$$$ ($$$0 \leq h_i \leq 10^6$$$)—the heights in pixels of the track.
Output "BUG REPORT" (without quotes) on a single line if it is impossible to pass that track; otherwise, output "POSSIBLE".
4 3 1 2 5 1 1
POSSIBLE
4 3 0 3 1 5 0
BUG REPORT
3 1000000 0 999999 1 1000000
POSSIBLE
Jayden is taking Computer Networks this semester and is currently learning about routers and IP address forwarding. His homework asks him to implement a technique called longest prefix matching to determine which entry in a router's lookup table corresponds to a given IP address. However, he is struggling and needs your help!
The router lookup table consists of $$$n$$$ entries, each consisting of a standard IP address and a subnet mask. For example, an entry could be:
In this example, $$$192.168.1.0$$$ is the IP address and $$$24$$$ is the mask. The binary representation of an IP address can be found by converting the four decimal numbers in the address to binary (base $$$2$$$) and adding zeros to the left until the result is $$$8$$$ digits long. For example, the above address would have the following binary representation:
The mask is the number of bits starting from the left that we need to match. In this example, all of the bits after the 24th bit are not important and will always be $$$0$$$, so we can ignore them:
Now, to check an IP address against this entry, we just check if the first 24 bits match. If they match, this would result in a matching of length 24. When we check an IP address against the lookup table, we are looking for the index of the entry that provides the longest matching. Consider the table from sample input 1:
| Index | Address |
| 1 | $$$11000000$$$.$$$10101000$$$.$$$00000001$$$.******** |
| 2 | $$$11000000$$$.$$$10101000$$$.$$$0011$$$****.******** |
| 3 | $$$11000000$$$.$$$10101000$$$.$$$00000001$$$.$$$1001$$$**** |
The first address we have to match is $$$192.168.1.148$$$ ($$$11000000$$$.$$$10101000$$$.$$$00000001$$$.$$$10010100$$$).
- The first entry matches with a length of 24, since the 24 bits not ignored are the same as the given address.
- The second entry does not match; the bits in the third group ($$$0011$$$****) are not the same as the given address.
- The third entry matches with a length of 28, since the 28 bits not ignored are the same as the given address.
If an address does not match any entries in the lookup table, print $$$-1$$$.
The first line of input contains two integers $$$n,m$$$ ($$$1 \leq n, m \leq 10^{3}$$$)—the number of entries in the lookup table and the number of IP addresses to match, respectively.
The next $$$n$$$ lines of input represent an entry in the lookup table, and will be of the format $$$a.b.c.d/e$$$ ($$$0 \leq a,b,c,d \leq 255, 0 \leq e \leq 32$$$). It is guaranteed that no two entries in the lookup table will match the same set of IP addresses.
The next $$$m$$$ lines of input represent an IP address to match. Each address will be of the format $$$a.b.c.d$$$ ($$$0 \leq a,b,c,d \leq 255$$$).
For each of the $$$m$$$ IP addresses to match, print the index of the longest prefix matching in the lookup table, or print $$$-1$$$ if it does not match anything in the lookup table.
3 3 192.168.0.1/16 192.168.82.1/24 192.168.140.16/20 192.168.131.255 192.168.13.37 192.167.131.255
3 1 -1
George's birthday is coming up, and his friends are excitedly planning his birthday party. They have already bought his presents and are now planning out the location for the party. After some deliberation, they have decided to host George's party in a mirror maze. Each section of the mirror maze consists of two parallel walls facing each other on which mirrors are placed. This creates the effect of seeing infinite reflections of oneself if you look at one of the walls.
George's friends did some research on how to build mirror mazes, and they discovered that a section of a mirror maze is fun only if the $$$k$$$-th reflection of the viewer appears $$$d$$$ meters away when the viewer looks at one of the mirrors. George's friends feel confident that they can now build the mirror maze, but they need help figuring out where to put the mirrors so that George will have the most fun. They are planning on building $$$n$$$ sections of the maze, and they know when George enters a section of the maze he will be looking to the left. For each section of the maze, they will build a mirror $$$x$$$ meters to the left of where George will be and $$$y$$$ meters to the right. Because of construction constraints, the distances $$$x$$$ and $$$y$$$ must be integers between $$$1$$$ and $$$10^9$$$. Help George's friends figure out where to place the mirrors for each section such that the $$$k$$$-th reflection is $$$d$$$ meters away or determine it is impossible to place the mirrors to construct a fun section.
The first line of input is $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of sections in the maze.
Each of the next $$$n$$$ lines will consist of two numbers $$$k$$$ and $$$d$$$ ($$$1 \leq k,d \leq 10^9$$$), where $$$d$$$ is the distance in meters where the $$$k$$$-th reflection should appear.
Output $$$n$$$ lines, one for each section of the maze. For each section, output two numbers, $$$x$$$ and $$$y$$$, the left and right distances of the mirrors, or "impossible" (without quotes) if no combination of left and right distances will result in the $$$k$$$-th reflection appearing $$$d$$$ meters away.
There may be more than $$$1$$$ pair of $$$x$$$ and $$$y$$$ that satisfy the constraints, you may print any such pair as long as $$$1 \leq x,y \leq 10^9$$$. It can be shown that if it is possible to place mirrors to create a fun section then there is a pair $$$x$$$ and $$$y$$$ such that $$$1 \leq x,y \leq 10^9$$$ which creates a fun section.
4 1 6 3 16 2 5 2 10
3 1 1 6 impossible 1 4
- In the first section of the maze, placing a mirror 3 meters to the left will cause the first reflection to appear 6 meters away.
- In the second section of the maze and by placing the mirrors 1 meter left and 6 meters right, the first reflection appears 2 meters away, the second reflection appears 14 meters away, and the third reflection appears 16 meters away.
- In the third section of the maze, no combination of integer distances will cause the second reflection to appear 5 meters away.
- In the fourth section of the maze, the first reflection appears 4 meters away and the second reflection appears 10 meters away.
Adeline and Byron are on a road trip through the mountains. Interestingly, the roads through the mountains can be modeled as a grid of size $$$ n \times m $$$, where each cell has an integer altitude. The grid follows standard Cartesian coordinates, with the top-left corner being $$$ (1,1) $$$ and the bottom-right corner being $$$ (n, m) $$$.
Adeline, an adrenaline junkie, loves the ups and downs of the mountains, while Byron gets motion sick easily. After some debate, they agreed on a compromise: they must find a route from their starting position $$$ (x_0, y_0) $$$ to their destination $$$ (x_f, y_f) $$$ that minimizes the total distance traveled, but to make it fun for Adeline, they must alternate between gaining and losing altitude with every move. If they take a longer path than necessary, Byron will get sick.
Adeline and Byron's car can move in any of the 8 cardinal directions: North, Northeast, East, Southeast, South, Southwest, West, and Northwest. Each movement to an adjacent cell counts as a distance of 1, regardless of direction.
Help Adeline and Byron determine the minimum number of moves required to reach their destination.
The first line contains two integers $$$ n $$$ and $$$ m $$$ $$$(1 \leq n, m \leq 500)$$$—the dimensions of the grid.
The next $$$ n $$$ lines each contain $$$ m $$$ integers $$$ h_{i,j} $$$ $$$(0 \leq h_{i,j} \leq 10^9)$$$, representing the altitude of each cell in the grid.
The next line contains four integers $$$ x_0, y_0, x_f, y_f $$$ $$$(1 \leq x_0, x_f \leq n, 1 \leq y_0, y_f \leq m)$$$—the starting and destination positions.
It is guaranteed that the starting and destination positions are distinct.
Print a single integer—the minimum number of moves required to reach $$$ (x_f, y_f) $$$ from $$$ (x_0, y_0) $$$, or print $$$-1$$$ if it is impossible to reach the destination.
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 4 5
9
1 4 1 2 3 1 1 1 1 4
-1
1 2 1 1 1 1 1 2
-1
Photo by Rosalind Chang on Unsplash Eugin and Kelly are celebrating E-Days at the Colorado School of Mines by participating in the annual Orecart Pull. This is an event where everyone walks the Orecart down Colfax Avenue all the way to downtown Denver. Eugin and Kelly can go faster than the group, so they have decided to break off and grab boba from every stop along the route!
The walk is $$$l$$$ meters long, and the Orecart moves at a constant speed of $$$1$$$ meter per second. Eugin and Kelly can run at a speed of at most $$$v$$$ meters per second, but they are not allowed to move ahead of the Orecart at any time.
There are $$$n$$$ boba stops along the route, the $$$i$$$-th of which is located at distance $$$d_i$$$ along the route. Additionally, at the $$$i$$$-th boba stop, they must wait at least $$$w_i$$$ seconds to receive their boba before continuing.
Eugin and Kelly need to visit all $$$n$$$ boba stops while ensuring that they reach the end at exactly the same time as the Orecart. Determine the minimum required speed $$$v$$$ for them to accomplish this.
If it is impossible for any finite speed to allow them to reach the end on time, or if the required speed would need to exceed the speed of light ($$$3 \cdot 10^8$$$ meters per second), output IMPOSSIBLE. Otherwise, print the minimum required speed $$$v$$$ with a relative error of at most $$$10^{-4}$$$.
The input consists of multiple lines:
- The first line contains two integers $$$n$$$ and $$$l$$$ $$$(1 \leq n \leq 10^5, 2 \leq l \leq 10^8)$$$—the number of boba stops and the length of the route.
- The second line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ $$$(0 \lt d_1 \lt d_2 \lt \dots \lt d_n \lt l)$$$—the distances at which each of the boba stops are located.
- The third line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ $$$(0 \leq w_i \leq 10^8)$$$—the waiting times at each boba stop.
If it is impossible to reach the end on time no matter the speed, or if the required speed would need to exceed $$$3 \times 10^8$$$ meters per second, print IMPOSSIBLE. Otherwise, print the minimum required speed $$$v$$$ such that the relative error does not exceed $$$10^{-4}$$$.
3 80 20 40 60 30 2 10
3.33333333
2 20 5 15 0 5
IMPOSSIBLE
At the prestigious Colorado School of Mimes, interdepartmental rivalries are both intense and theatrical. Each department considers exactly one other department as their rival. However, rivalries are not always reciprocated—a department may view another as their rival without that feeling being mutual.
The administration, seeking to foster cooperation despite these rivalries, has decided to form rivalry pairs for an upcoming school-wide fundraising event. Each rivalry pair consists of two departments where either:
- One department considers the other as a rival, or
- They consider each other as rivals.
The administration wants to maximize the number of rivalry pairs to have as many departments as they can at the fundraising event, but due to the asymmetric nature of rivalries, it may not be possible to pair up every department. Some departments will be left without a pair.
Given the rivalry preferences of all departments, and that the administration will maximize the number of departments at the event, determine the minimum number of departments that cannot be paired.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of departments.
The second line contains $$$n$$$ space-separated integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \leq r_i \leq n$$$), where $$$r_i$$$ represents the department that department $$$i$$$ considers as its rival. A department may consider itself a rival, i.e., $$$r_i = i$$$.
Print a single integer—the minimum number of departments that cannot be paired.
5 2 3 1 5 4
1
4 2 1 4 3
0