Problem E
Graph Data Structure 1

VisuAlgo – a web-based tool for visualising data structures and algorithms through animation – has a Graph Data Structure visualization https://visualgo.net/en/graphds. In that visualization, a user can edit any of the many example graphs or draw/input their own graph. Each graph in this visualization is a simple graph: a graph that does not have more than one edge between any two vertices and no edge that starts and ends at the same vertex. In short, a simple graph is a graph without self-loops and multi-edges. Note that the graph can be directed or undirected.

There are a few special graphs that can be automatically detected in that visualization. For this problem, we want to detect these four special graphs given an input graph with $N$ vertices and $M$ edges. The graph’s vertices are $0$-indexed, i.e. they are numbered from $0$ to $N - 1$.

1. Tree-s are undirected graphs in which any two vertices are connected by exactly one simple path. In other words, trees are connected acyclic undirected graphs. An undirected tree is also a bipartite graph – see below. A Directed Acyclic Graph (DAG) – see below – is also a tree if it is connected and the only vertex with in-degree zero (the root) can reach all other vertices. If a tree has $N$ vertices, it will have $M = N-1$ edges.

2. Complete Graph-s are undirected graphs in which every pair of distinct vertices is connected by a unique edge. In other words, every vertex in a complete graph is adjacent to all other vertices. A directed graph can also be considered a Complete Graph if every pair of distinct vertices $(u, v)$ is connected by two unique directed edges $(u, v)$ and $(v, u)$. If a complete undirected graph has $N$ vertices, it will have $M = N \cdot (N-1)/2$ edges. A complete directed graph of $N$ vertices has twice the edges from its undirected counterpart.

3. Bipartite Graph-s are graphs whose vertices can be divided into two disjoint and independent sets $U$ and $V$. That is, every edge connects a vertex in $U$ to a vertex in $V$. Bipartite Graph can be defined on directed graph too, but all edge directions must be from a vertex in $U$ to a vertex in $V$.

4. Directed Acyclic Graph (DAG)-s are directed graphs with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a cycle. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. By default, an undirected graph with at least one undirected edge is not a DAG.

Input

Each test case describes a simple graph $G = (V, E)$.

The first line contains three integers, $N$, $M$, and $T$ $(1 \le N \le 100\; 000$, $0 \le M \le 200\; 000$, $1 \le T \le 2)$. Then the next $M$ lines contains the edges, each consisting of two integers, $u$ and $v$ ($0 \le u, v < N$).

If $T = 1$ (undirected), each edge $(u, v)$ is undirected. Furthermore, $M \le N \cdot (N-1)/2$ also holds.

If $T = 2$ (directed), each edge $(u, v)$ is directed, the direction is from $u$ to $v$. Furthermore, $M \le N \cdot (N-1)$ also holds.

It is guaranteed that the graph does not contain any self-loops or multi-edges.

Output

For each input graph $G$, print 4 integers: $a$, $b$, $c$, and $d$ in one line, separated with a single space.
Put $a = 1$ if $G$ is a tree, or $a = 0$ otherwise.
Put $b = 1$ if $G$ is a complete graph, or $b = 0$ otherwise.
Put $c = 1$ if $G$ is a bipartite graph, or $c = 0$ otherwise.
Put $d = 1$ if $G$ is a DAG, or $d = 0$ otherwise.

Subtasks

1. ($7$ Points): Only contains the following input:

                   5 4 1
                   2 3
                   1 0
                   4 1
                   1 2
           

2. ($17$ Points): All graphs in this subtask are either a tree (and also a bipartite graph) or a general graph, $N \ge 3$, $T = 1$.

3. ($10$ Points): All graphs in this subtask are either a complete graph or a general graph, $N \ge 3$, $T = 1$.

4. ($21$ Points): All graphs in this subtask are either a bipartite graph or a general graph, $N \ge 3$, $T = 1$.

5. ($22$ Points): All graphs in this subtask are either a Directed Acyclic Graph or a general graph, $T = 2$.

6. ($23$ Points): No additional constraints. There are $23$ test cases in this subtask and each correct identification worth 1 point.

Explanation of Subtask 1

The following is the illustration of the undirected graph in Subtask 1.

3 2 1
0 1
0 2

1 0 1 0

4 6 1
0 1
0 2
0 3
1 2
1 3
2 3

0 1 0 0

3 2 2
2 0
2 1

1 0 1 1

3 3 2
0 1
1 2
0 2

0 0 0 1