Mr.Frog wants to travel all over the country, and as we all know the country consists of N cities and M directed roads connecting these cities. The cities are numbered from 1 to N. The roads are numbered from 1 to M, the ith road connects the city Ui to Vi which means Mr.Frog can move to city Vi from city Ui. Mr.Frog wants to travel all cities, and he can choose a city to start his trip casually and choose a city to end his trip casually. In order to avoid the boredom in the journey, Mr.Frog decides to make a plan that can help him arrive each city exactly once and pass through each road exactly once. Now give you the information of the cities and roads. Please tell Mr.Frog whether there exists a way that can satisfy his plan.
Mr.Frog wants to travel all over the country, and as we all know the country consists of N cities and M directed roads connecting these cities. The cities are numbered from 1 to N. The roads are numbered from 1 to M, the ith road connects the city Ui to Vi which means Mr.Frog can move to city Vi from city Ui. Mr.Frog wants to travel all cities, and he can choose a city to start his trip casually and choose a city to end his trip casually. In order to avoid the boredom in the journey, Mr.Frog decides to make a plan that can help him arrive each city exactly once and pass through each road exactly once. Now give you the information of the cities and roads. Please tell Mr.Frog whether there exists a way that can satisfy his plan.