Domácí kolo

G: Jednosměrky

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Michal pracuje v cestovce, která dělá prohlídky centra Prahy autobusem.

V centru Prahy je N křižovatek očíslovaných 1 až N, a M jednosměrných ulic. Každá ulice spojuje nějaké dvě křižovatky. Cestu, která by začala na nějaké křižovatce, šla po jednosměrkách a dostala se zpět na původní křižovatku, nazveme cyklus. Aby v centru nebylo moc aut, žádné cykly tu nejsou.

Prohlídky vždy začínají na křižovatce 1 (u které mají autobusy depo) a končí na křižovatce N (přímo před spřízněným obchodem s matrjoškami).

Michal by chtěl, aby byly prohlídky co nejrozmanitější. Proto by si přál, aby se z křižovatky 1 na křižovatku N dalo dostat co nejvíce různými způsoby. Cestovka naštěstí zalobbovala a domluvila, že si může vybrat jednu ulici a obrátit její směr. Vybrat si ale může jen některé (i lobbing má své meze). Je povolené i nezměnit směr žádné ulice. Slibujeme, že:

  • obrácením směru libovolné povolené ulice nevznikne cyklus
  • z křižovatky 1 se dá dostat na každou jinou, a z každé se dá dostat do N
  • cest z 1 do N po obrácení až jedné jednosměrky vznikne maximálně 1018

Kolik nejvíc cest může vést z křižovatky 1 do křižovatky N?

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na jednom řádku čísla N a M. Následuje M řádků tvaru Ui Vi Pi, značící, že i-tá ulice vede z Ui do Vi. Pi je 1, pokud je povoleno změnit její směr, jinak 0.

Tvar výstupu

Pro každý problém vypište jeden řádek s maximálním počtem cest z křižovatky 1 do křižovatky N, když provedeme až jednu výše popsanou změnu.

Lehká verze

  • T ≤ 10
  • N, M ≤ 500

Těžká verze

  • T ≤ 10
  • N, M ≤ 100 000

Ukázkový vstup

2
5 7
1 2 1
2 4 1
2 5 0
1 3 1
1 4 0
3 4 1
4 5 1
3 3
1 2 1
2 3 1
1 3 0

Ukázkový výstup

5
2

Vysvětlení ukázkového vstupu a výstupu

V prvním testu se vyplatí obrátit jednosměrku, která původně vede z křižovatky 2 do křižovatky 4. Počet cest se tak zvýší ze 4 na 5.

V druhém testu je nejlepší nic neobracet.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)