맛집 탐방

은수는 맛집을 탐방하러 도시로 여행을 떠날 것이다. 도시에는 총 $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을 출력한다.