No.1563 Same Degree
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 127
作問者 : maguro / テスター : blackyuki PCTprobability
タグ : / 解いたユーザー数 127
作問者 : maguro / テスター : blackyuki PCTprobability
問題文最終更新日: 2021-06-25 21:30:37
問題文
$N$ 頂点 $M$ 辺の単純グラフ $G$ が与えられます。 $i\ (1 \leq i \leq M)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結びます。
$G$ に次数が等しい頂点の組 $(a,b)\ (a \neq b)$ は存在しますか?
$T$ 個のケースが与えられるので、それぞれについて答えを求めてください。
入力
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
各ケースは以下のように与えられる。
$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$
- 入力は全て整数である。
- $1 \leq T \leq 10^4$
- $1 \leq N \leq 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq u_i,v_i \leq N$
- $u_i \neq v_i$
- $(u_i,v_i) \neq (u_j,v_j)\ (i \neq j)$
- $(u_i,v_i) \neq (v_j,u_j)\ (i \neq j)$
- $1$ つのテストケースにおいて、 $N$ の総和は $10^5$ を超えない。
- $1$ つのテストケースにおいて、 $M$ の総和は $2 \times 10^5$ を超えない。
出力
$T$ 行にわたって出力してください。
$i\ (1 \leq i \leq N)$ 行目には、 $case_i$ について、次数が等しい頂点の組が存在するならYes
を、存在しないならNo
を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 5 5 1 3 2 5 5 3 4 2 2 1 2 1 1 2
出力
Yes Yes
$1$ つ目のケースでは、例えば頂点 $1$ と頂点 $3$ はともに次数が $2$ です。
$2$ つ目のケースでは、頂点 $1$ と頂点 $2$ はともに次数が $1$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。