問題文
0個の頂点と0本の辺からなる無向グラフがあります。
個のクエリが与えられるので、順に処理してください。個目のクエリは以下の通りです。
- グラフに頂点を追加する。について、とが互いに素でなければ頂点と頂点を辺で結ぶ。 その後、頂点と連結な頂点の個数を出力する。
制約
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
の答えを空白区切りで出力せよ。
サンプル 1
入力
6
4 5 8 12 25 9
出力
1 1 2 3 2 4
の処理後、頂点1は孤立です。
の処理後、頂点2は孤立です。
の処理後、頂点1,3が連結です。
の処理後、頂点1,3,4が連結です。
の処理後、頂点2,5が連結です。
の処理後、頂点1,3,4,6が連結です。
サンプル 2
入力
10
4 9 5 22 35 7 6 9 13 27
出力
1 1 1 2 2 3 4 5 1 6
サンプル 3
入力
100
75 69 40 74 47 29 28 9 95 82 12 91 64 98 32 6 79 12 10 63 62 16 15 67 5 19 6 97 98 92 9 45 55 12 15 11 52 25 44 24 50 55 91 63 22 27 37 73 55 14 60 83 96 8 46 92 75 2 4 85 46 4 40 58 27 10 95 47 45 47 31 88 29 96 3 81 87 86 4 46 15 2 71 35 39 80 42 51 3 17 20 7 82 2 44 56 57 42 44 33
出力
1 2 3 4 1 1 5 6 7 8 9 10 11 12 13 14 1 15 16 17 18 19 20 1 21 22 23 1 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 1 43 44 45 1 46 47 48 49 50 51 52 53 54 55 56 58 59 60 61 2 62 3 63 64 65 66 67 68 69 70 71 72 73 74 1 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする