- Zajęcia w szkołach
- Informatyka i Ty
- O portalu
- Mapa portalu
J - Jack's socks
Time limit: 11 s
Jack is a scientist. As you probably realize, this means he does not pay much attention to what he wears daily. He is also a man, which means that he knows the names of no more than six colors, cannot tell the difference between ecru and white and associates plum only with fruits. But today he is leaving for a conference. He has just pulled a set of single socks out of washing machine and must pair them. He can say which sock is similar to which one, and he may pair only these socks which seem similar. However, many socks are similar to many others. Worse than that, similarity relation is not necessarily transitive. For example, for Jack blue feels similar to seagreen and seagreen to green, but Jack can distinguish between blue and green and say that they are not similar.
Jack wonders if there is exactly one way to pair all his socks. Help him by writing an appropriate program. Do not worry: he might be a scientist, but he is not going to wear his socks with sandals.
Multiple Test Cases
The input contains several test cases. The first line of the input contains a positive integer , denoting the number of test cases. Then test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.
Single Instance Input
The first line of input instance contains two integers and separated by a single space, where and . Number is even and denotes the number of socks; they are numbered from to . Each of the following lines contains two numbers separated by a single space, which means that socks and are similar. Each similarity pair is listed exactly once, i.e., if occurs, then neither nor appears later in this list.
Single Instance Output
For each input instance your program should check whether there exists exactly one way of pairing all these socks. If not, it should output a line containing NO. Otherwise, it should output YES in the first line, followed by lines, each containing a sock pair from this pairing separated by a single space. Pairs should be output in sorted order, i.e., for each pair , it should hold that and for any two consecutive pairs and , .
2 4 4 1 2 2 3 3 4 4 1 4 3 1 2 2 3 3 4
NO YES 1 2 3 4
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.