Restaurant Tour

Time limit3sMemory limit1024 MB

Summary

Given a directed graph of N restaurants and M one-way roads, decide whether one walk can cover all restaurants, all roads, or both.

Level: Medium6 of 10
Topics: Graph, Topological sort, DFS
Solved: No attempts yet

Problem

Eunsu is going to travel to a city to tour its restaurants. The city has $N$ restaurants in total. The city has $M$ one-way roads that let you move from one restaurant to another, and each road has a souvenir shop halfway along it. A road may start and end at the same restaurant, and several roads may connect the same pair of restaurants. Eunsu starts at any restaurant, moves along roads from restaurant to restaurant, and ends at any restaurant. The start and end do not need to be the same. The city is far from Eunsu's village, so Eunsu wants to visit as many restaurants and shops as possible on one trip. If a trip visits every restaurant, or every souvenir shop, Eunsu gets a discount on the next trip. Eunsu wants to know whether such a trip is possible. Your task is to plan the trip.

Input

The first line contains $N$ and $M$ , separated by a space ( $1 \leq N, M \leq 500\,000$ ). Each of the next $M$ lines contains two integers $u$ and $v$ , separated by a space, which means there is a one-way road from restaurant $u$ to restaurant $v$ ( $1 \leq u, v \leq N$ ).

Output

Print three lines. The first line prints 1 if Eunsu can plan a trip that visits all $N$ restaurants, and 0 otherwise. The second line prints 1 if Eunsu can plan a trip that visits all $M$ souvenir shops, and 0 otherwise. The third line prints 1 if Eunsu can plan a trip that visits all $N$ restaurants and all $M$ souvenir shops, and 0 otherwise.

Examples2

Example 1
Input
```
4 6
1 2
1 4
2 3
2 4
3 1
3 4
```
Expected output
```
1
0
0
```
Example 2
Input
```
3 2
1 3
2 1
```
Expected output
```
1
1
1
```