20560번 - 맛집 탐방

은수는 맛집을 탐방하러 도시로 여행을 떠날 것이다. 은수가 갈 도시에는 총 $N$개의 맛집이 있다.

도시에는 맛집에서 맛집으로 이동할 수 있는 일방통행 길이 $M$개 있고, 각 길의 중간에는 기념품 상점이 있다. 어떤 길은 출발하는 맛집과 도착하는 맛집이 같을 수도 있으며, 여러 길이 같은 맛집을 연결할 수도 있다.

은수는 도시의 맛집에서 여행을 시작해서, 길을 이용해 맛집을 탐방하다 도시의 맛집에서 여행을 끝낼 것이다. 여행을 시작한 곳과 여행을 끝낸 곳이 같을 필요는 없다.

도시는 은수가 사는 마을에서 멀리 떨어져 있기 때문에, 은수는 한 번의 여행에서 최대한 많은 맛집과 상점을 들르려고 한다. 특히, 여행 중에 모든 맛집을 방문하거나 모든 기념품 상점을 방문한다면 다음 여행에서 할인 혜택을 받을 수 있기 때문에 은수는 이런 여행이 가능한지 알고 싶어 한다. 우리가 할 일은, 은수의 여행 계획을 돕는 것이다.

첫 번째 줄에 맛집의 수 $N$과 길의 수 $M$이 공백으로 구분되어 주어진다. ($1 \leq N, M \leq 500\,000$)

두 번째 줄부터 $M$줄에 걸쳐 각 길의 정보가 주어진다. 각 줄에는 두 수 $u$, $v$가 공백으로 구분되어 주어지는데, 이는 맛집 $u$에서 맛집 $v$로 가는 길이라는 것을 의미한다. ($1 \leq u, v \leq N$)

총 3개의 줄을 출력한다.

첫 번째 줄에는 은수가 $N$개의 맛집을 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.

두 번째 줄에는 은수가 $M$개의 기념품 상점을 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.

세 번째 줄에는 은수가 $N$개의 맛집을 모두 방문하면서, $M$개의 기념품 상점도 모두 방문할 수 있는 여행 계획이 존재하면 1을, 그렇지 않다면 0을 출력한다.