C. Валера ба сонгууль

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Валерагын амьдардаг хотод Парламентын сонгууль явагдах гэж байгаа.

Хотод $n$ дүүрэг, $n - 1$ хоёр урсгалтай зам байдаг. Бид аль ч дүүргээс замаар явж бусад бүх дүүрэгрүү очиж болдог гэдгийг мэдэж байгаа. Дүүргүүдийг $1$-ээс $n$-ийн хооронд дугаарласан. Түүнчлэн оршин суугчид замуудыг эвдрэлтэй, эвдрэлгүй гэж ангилсан. Эвдрэлтэй зам гэдэг нь засагдах шаардлагатай зам юм.

Сонгууль $n$ нэр дэвшигч өрсөлдөж байгаа бөгөөд тэднийг $1$-ээс $n$-ийн хооронд дугаарлая. Хэрвээ $i$ дугаартай нэр дэвшигч Парламентэд сонгогдвол тэр заавал $i$-р дүүрэгээс $1$-р дүүрэг хүртлэх эвдрэлтэй замуудыг бүгдийг нь засах ёстой.

Валерад туслан нэр дэвшигчдийн дэд олонлогыг ол. Тухайн сонгох дэд олонлогын элемент буюу нэр дэвшигчид бүх эвдрэлтэй замуудыг засаж байхаар хамгийн цөөн нэр дэвшигчтэй байх ёстой юм.

Оролт

Эхний мөрөнд хотын дүүргийн тоо болох нэг ширхэг бүхэл тоо $n$ ($2 ≤ n ≤ 10^5$) өгөгдөнө.

Дараагийн $n - 1$ мөр бүрт гурван бүхэл тоо $x_i$, $y_i$, $t_i$ ($1 ≤ x_i, y_i ≤ n$, $1 ≤ t_i ≤ 2$) - $i$ хоёр урсгалтай замын хувьд $t_i$ нь $1$-тэй тэнцүү байвал $x_i$, $y_i$ дүүргийн хооронд эвдрэлгүй зам байгааг илэрхийлнэ. Харийн $t_i$ нь $2$ байвал $x_i$, $y_i$ дүүргийн хооронд эвдрэлтэй зам байгааг илэрхийлнэ.

Өгөгдсөн граф заавал мод байна.

Гаралт

Эхний мөрөнд нэг ширхэг тоо болох нэр дэвшигчдийн дэд олонлогийн элементийн тоо $k$-г хэвлэнэ. Дараагийн мөрөнд нэр дэвшигчдийн индексийг агуулах $k$ элементтэй $a_1, a_2, ... a_k$ дарааллыг хэвлэ. Хэрвээ олон шийд байвал алийг нь ч хэвлэж болно.

Орчуулсан: byambadorjp

Жишээ тэстүүд

Оролт
5
1 2 2
2 3 2
3 4 2
4 5 2
Гаралт
1
5 
Оролт
5
1 2 1
2 3 2
2 4 1
4 5 1
Гаралт
1
3 
Оролт
5
1 2 2
1 3 2
1 4 2
1 5 2
Гаралт
4
5 4 3 2 
Сэтгэгдлүүдийг ачааллаж байна...