No.92 逃走経路
問題文
Yuki City は $N$ 個の町と $M$ 本の道路からなる。
町は $1$ から $N$ まで番号が振られている。
道路は双方向に通行でき、それぞれ通行料金が設定されている。
さて、Yuki City 警察のあなたはある指名手配犯を追っている。
長らく犯人の居場所を掴めなかったあなただが、つい先日有力な情報を手に入れた。
その情報とは、犯人が支払った通行料金のうち、直近 $K$ 回分を時系列順に並べたものである。
あなたはこの情報を使い、犯人が今いる可能性のある町を絞り込みたい。
警察官であると同時に天才プログラマーでもあるあなたは、プログラムによってこの問題を解こうと考えた。
入力
$N$ $M$ $K$ $a_1$ $b_1$ $c_1$ $\vdots$ $a_M$ $b_M$ $c_M$ $d_1$ $\ldots$ $d_K$
$1$ 行目に $N,M,K$ が空白区切りで与えられる。
続く $M$ 行に正整数 $a_i,b_i,c_i$ が空白区切りで与えられる。
これは、町 $a_i$ と町 $b_i$ が通行料金 $c_i$ の道路で結ばれていることを表す。
最終行に $K$ 個の正整数 $d_i$ が空白区切りで与えられる。
これは、犯人が支払った通行料金のうち、直近 $K$ 回分を時系列順に並べたものである。
$2\leq N\leq100$
$1\leq M,K\leq1,000$
$1\leq a_i<b_i\leq N$
$1\leq c_i,d_i\leq10^9$
出力
$1$ 行目に犯人が今いる可能性のある町の個数を出力せよ。
$2$ 行目にそのような町の番号を昇順に空白区切りで出力せよ。
最後に改行してください。
犯人が今いる可能性のある町は少なくともひとつ存在する。
サンプル
サンプル1
入力
3 2 2 1 2 10 2 3 20 10 20
出力
1 3
犯人は通行料金 $10$ の道路を通り、続いて通行料金 $20$ の道路を通った。
ここから犯人は今町 $3$ にいると分かる。
サンプル2
入力
3 2 2 1 2 10 1 2 20 10 20
出力
2 1 2
ある町のペアを複数本の道路が結ぶこともある。
また、どの町のペアも互いに行き来できるとは限らない。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。