ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1320. Graph Decomposition

Time limit: 0.5 second
Memory limit: 64 MB
There is a simple graph with an even number of edges. You are to define if it is possible to present it by the set of pairs of adjacent edges (having a common vertex).

Input

contains a non-empty sequence of the integers pairs. The length of the sequence is even and is from 2 to 1050. Each pair of integers denotes vertices identifiers of one edge. All the identifiers are from 1 to 1000. You may assume that there are no loops and multiple edges in the graph defined by the input data.

Output

“1” (without quotation marks), if the decomposition is possible and “0” otherwise.

Samples

inputoutput
1 2
2 3
3 1
1 10
1
1 2
2 3
3 1
4 10
0
Problem Author: Idea: Alexander Petrov, prepared by Alexander Petrov, Leonid Volkov
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004