問題一覧 > ネタ問題

No.8107 Listening

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 28
作問者 : harurun / テスター : yuusanlondon
お気に入りにしたユーザー ProblemId : 10442 / 自分の提出
問題文最終更新日: 2024-03-07 05:25:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder April Fool Contest 2024 (順位表) の他の問題:

Problem Statement

Input

$N\ M$
$u_1\ v_1$
$\vdots$
$u_M\ v_M$
  • $2≤N≤2\times 10^5$
  • $N-1≤M≤min(N(N-1)/2,10^6)$
  • $1≤u_i,v_i≤N$
  • $u_i\ne v_i$
  • $i\ne j \Rightarrow \{u_i,v_i\}\ne \{u_j,v_j\}$
  • All inputs are integers.
  • The given graph is simple, undirected, and connected.

Output

Let $S$ be a set of edge indices satisfying the conditions in the problem statement.

$|S|$
$S_1$
$\vdots$
$S_{|S|}$

First, print the size of $S$ on the first line.

Then, print each edge index contained in $S$ exactly once, one per line.

If there are multiple answers, any of them will be accepted.

Sample

Sample 1
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
2
1
6

The given graph is as shown in the figure below.

The graph in the figure below is a maximum matching of the given graph. In this case, $S=\{1,6\}$.

The elements of $S$ may be printed in any order.

The following output is also accepted.

2
2
5

This output also gives a maximum matching of the given graph.

Sample 2
Input
5 5
1 2
2 3
3 4
4 5
5 2
Output
2
1
4

This output is a maximum matching of the given graph.

Sample 3
Input
6 5
1 2
6 2
6 3
6 4
6 5
Output
2
1
3

This output is a maximum matching of the given graph.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。