Fişierul intrare/ieşire:comoditate.in, comoditate.outSursăONIS 2015, Runda 2
AutorMihai CalanceaAdăugată depas.andreiPopovici Andrei-Sorin pas.andrei
Timp execuţie pe test2.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Comoditate

Giani, cel mai mare Mai Mare al Oraşului, este foarte mulţumit de infrastructura din Oraş. Oraşul are N intersecţii şi M străzi bidirecţionale care leagă fiecare câte o pereche de intersecţii. Infrastructura este atât de solidă, încât dacă vreuna din intersecţii s-ar închide, încă ar fi posibil să se ajungă din orice intersecţie deschisă în orice altă intersecţie deschisă mergând pe străzi existente. Giani ştie că progresul înseamnă să te străduieşti permanent să faci viaţa mai comfortabilă pentru cetăţenii tăi. Astfel, gândindu-se la comfortul său, Giani a realizat că i-ar plăcea foarte mult să nu fie nevoit să se uite în ambele direcţii atunci când trece strada. Giani vă cere să daţi un sens unic fiecărei străzi existente, astfel încât pentru oricare 2 intersecţii X şi Y, X să fie accesibilă din Y şi invers (respectând bineînţeles sensul de mers dat străzii).

Date de intrare

Fişierul de intrare comoditate.in va conţine pe prima sa linie numărul de teste T. Fiecare test are următoarea structură: prima linie conţine două valori N şi M, reprezentând numărul de intersecţii, respectiv numărul de străzi din oraş. Următoarele M linii conţin câte o pereche de numere X Y, semnificând faptul că intersecţiile X şi Y sunt legate printr-o stradă bidirecţională.

Date de ieşire

Fişierul de ieşire comoditate.out va conţine T soluţii, pentru fiecare oraş din input. Fiecare soluţie va fi un şir de caractere de lungime M. Al i-lea caracter al şirului va fi egal cu 0 dacă strada cu numărul i din testul respectiv va fi orientată dinspre oraşul cu indice mai mic către oraşul cu indice mai mare, sau 1 altfel.

Restricţii

  • 1 ≤ T ≤ 100
  • 3 ≤ N ≤ M ≤ 100.000
  • Suma tuturor valorilor M în cadrul aceluiaşi fişier de intrare nu va depăşi valoarea 3.000.000
  • Fiecare oraş din fişierul de intrare respectă proprietatea conform căruia ar rămâne conectat în întregime chiar dacă s-ar închide vreuna din intersecţii.

Exemplu

comoditate.incomoditate.out
1
3 3
1 2
1 3
2 3
010

Explicaţie

Străzile vor avea orientarea 1 -> 2, 2 -> 3, 3 -> 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?