Return to the Index of Readings and Problem Sets

15-295 Reading 5 (Wednesday, February 16, 2005)

Assigned Readings

Problem A: Coffee machines

A university campus includes several buildings, some of which are connected by corridors; two buildings may have at most one corridor between them, which means that the corridors form a well-defined undirected graph. The university administration has decided to install new coffee machines throughout the campus, in such a way that students can always get coffee without going outside the buildings. Thus, if several buildings are connected by corridors, they need only one coffee machine; on the other hand, if two buildings are not connected by any chain of corridors, they require two different machines. Your task is to write a program that determines the minimal required number of machines.

Input

The first line contains a positive integer n between 1 and 100,000, which is the number of buildings; the other lines describe corridors between buildings, one corridor per line. The description of a corridor includes two distinct integers between 1 and n, separated by a single space, which represent the buildings connected by this corridor; for example, the line "2 4" describes a corridor between buildings 2 and 4. The total number of corridors is at most 1,000,000; the last line is "0 0", which does not represent a corridor.

Output

The output is a single integer number, which represents the minimal required number of coffee machines.

Sample input

6
1 2
2 3
4 5
0 0

Sample output

3

Problem B: Counterintelligence

The country of Big Endians is at war with the neighboring country of Little Endians, and the Big-Endian police has recently discovered a network of Little-Endian spies. Since the Big-Endian police intercepts phone and e-mail communications, the spies use pigeons to deliver sensitive information. This strategy helped them to remain undetected for a long time, but eventually the police has mapped all pigeon routes. Each route is a one-way communication channel between two spies, which means that these routes form a directed graph. The police believes that the network may include a spymaster, who collects information from all other spies and never sends anything back; that is, every spy has a direct pigeon route to the spymaster, whereas the spymaster does not send pigeons to anyone. Your task is to write a program that helps the police to identify the spymaster.

Input

The first line contains a positive integer n between 1 and 100,000, which is the number of spies; the other lines describe pigeon routes, one route per line. The description of a route includes two distinct integers between 1 and n, separated by a single space; the first integer is the spy sending a pigeon, and the second is the receiving spy. The total number of pigeon routes is at most 1,000,000; the last line is "0 0", which does not represent a route.

Output

If the network includes a spymaster, the output is a single integer number, which represents the spymaster; else, the output is the string "No spymaster."

Sample input

4
1 2
1 3
3 1
3 2
4 1
4 2
4 3
0 0

Sample output

2

Problem C: Odd artwork

The modern art sometimes looks strange, and critics may disagree whether a specific abstract sculpture is a true piece of art, or just a pile of broken appliances. A famous abstract artist has recently presented a new controversial sculpture; it consists of small rubber balls, connected by wires, which form a complex undirected graph in three dimensions. The artist claims that this graph does not have cycles with odd number of edges, and that its main artistic value is the absence of such cycles. Since this structure includes a huge number of balls and wires, critics cannot verify the absence of odd-length cycles, and they are skeptical about the artist's claim. Your task is to write a program that checks whether the artist is right.

Input

The first line contains a positive integer n between 1 and 100,000, which is the number of rubber balls; the other lines describe wires, one wire per line. The description of a wire includes two distinct integers between 1 and n, separated by a single space, which represent the balls connected by this wire. The total number of balls is at most 1,000,000; the last line is "0 0", which does not represent a wire.

Output

If the sculpture has no cycles with an odd number of edges, the output is "The artist is right"; else, it is "The artist is wrong".

Example input

6
1 2
1 3
2 4
3 4
3 5
4 6
5 6
0 0

Example output

The artist is right