Tourists in Mancunia
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The grand kingdom of Mancunia is famous for its tourist attractions and visitors flock to it throughout the year. King Mancunian is the benevolent ruler of the prosperous country whose main source of revenue is, of course, tourism.
The country can be represented by a network of unidirectional roads between the cities. But Mancunian, our benign monarch, has a headache. The road network of the country is not tourist-friendly and this is affecting revenue. To increase the GDP of the nation, he wants to redirect some of the roads to make the road network tourist-friendly and hence, ensure happiness and prosperity for his loyal subjects.
Now is the time for some formal definitions. :(
A road network is said to be tourist-friendly if for every city in the country, if a tourist starts his journey there, there is a path she can take to visit each and every city of the nation and traverse each road exactly once before ending up at the city where she started.
Given a description of the road network of Mancunia, can you come up with a scheme to redirect some (possibly none) of the roads to make it tourist-friendly?
The first line contains two integers N and E denoting the number of cities and roads in the beautiful country of Mancunia respectively.
Each of the next E lines contains two integers a and b implying that there is a unidirectional road from city a to city b.
It is guaranteed that there aren't multiple roads in the exact same direction and that there is no road from a city to itself.
If there is no solution, print "NO" (without quotes). Else, print "YES" (without quotes), followed by exactly E lines.
The ith line of output should represent the ith road in the input. It should have two integers a and b denoting that the final orientation of that road is from a to b.
- 1 ≤ N ≤ 100000
- 1 ≤ E ≤ 200000
- 1 ≤ a, b ≤ N
Subtask 1: (20 points)
- 1 ≤ N ≤ 20
- 1 ≤ E ≤ 21
Subtask 2: (80 points)
- Same as original constraints
Input: 3 3 1 2 2 3 3 1 Output: YES 1 2 2 3 3 1
Input: 3 2 1 2 2 3 Output: NO
Input: 5 6 1 2 2 3 3 4 2 4 2 5 1 5 Output: YES 1 2 2 3 3 4 4 2 2 5 5 1
|Tags||easy, eulerian, graph, jan17, satyaki3794|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.