Not Cycle Gragh?

問題文

この問題は only-output (出力のみの問題) である。

以下の問題を問題Aとする。

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる。頂点には $1,2,...,N$ の番号が、辺には $1,2,...,M$ の番号がつけられており、辺 $i$ は頂点 $A_i$ と頂点 $B_i$ を結んでいる。

このグラフがサイクルグラフかどうか判定せよ。

この 問題A について、初心者コーダーのmoguさんは次のような判定方法を考え、コードとして実装した。

• 以下の条件を全て満たせばサイクルグラフである。
  • 全ての頂点について、その次数(その頂点からの辺の本数)は $2$ である。
  • 任意の頂点について、その頂点から同じ辺を $2$ 回使うことなく頂点間を移動して帰ってこれるような経路が存在する。

moguさんのコードを撃墜できるようなテストケースを $1$ つ生成せよ。

単純無向グラフとは

単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいう。

サイクルグラフとは

頂点に $1,2,...,N$ の番号が付けられた $N$ 頂点のグラフがサイクルグラフであるとは、 $(1,2,...,N)$ を並べ変えて得られる数列 $(v_1,v_2,...,v_N)$ であり、 以下の条件を満たすものが存在することをいう。

• $i = 1,2,...,N-1$ に対し、頂点 $v_i,v_{i+1}$ を結ぶ辺が存在する。
• 頂点 $v_N,v_1$ を結ぶ辺が存在する。
• それら以外の辺は存在しない。

制約

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• $i \neq j$ ならば $(A_i,B_i) \neq (A_j,B_j),(B_j,A_j)$

入力

入力は与えられない。

出力

moguさんのコードを撃墜できるようなテストケースを $1$ つ、以下の形式で出力せよ。

N M
A_1 B_1
A_2 B_2
...
A_M B_M

サンプル

3 3
1 2
2 3
3 1

このテストケースで与えられるグラフはサイクルグラフであり、moguさんの判定方法においてもサイクルグラフと正しく判定されるので、このテストケースはWAとなります。

4 3
1 2
2 3
3 4

このテストケースで与えられるグラフはサイクルグラフではなく、moguさんの判定方法においてもサイクルグラフでないと正しく判定されるので、このテストケースはWAとなります。