U jednoj državi postoji n gradovo i m dvosmernih auto-puteva između nekih od njih. Svaki grad ima neku vrednost v iz skupa {1, 2, ..., n}, pri čemu ne postoje dva grada sa istom vrednošću. Ove vrednosti predstavljaju indekse popularnosti i grad sa vrednošću n je gravni grad.

Odlučeno je da neke od puteva u ovoj državi treba asfaltirati, pri čemu će asfaltiranje finansirati gradovi. Svaki grad je rekao da će asfaltirati (tačno jedan) put koji vodi od njega do njegovog suseda sa najvećom vrednošću (jer je to u interesu svakog grada). Međutim, ukoliko je vrednost nekog grada veća od svih njegovih suseda on ne asfaltira nijedan put.

Mi smo stranci i ne znamo vrednosti gradova, ali imamo mapu i zbamo koji su putevi asfaltirani. Ukoliko ima tačno n - 1 asfaltiranih puteva, odrediti sve gradove koji mogu biti glavni. Garantuje se da postoji bar jedan takav grad, tj. mapa je zadata korektno.

Ulaz:

(Ulazni podaci se učitavaju iz datoteke asfalt.in.) U prvom redu ulaza nalaze se 2 prirodna broja n i m, koji predstavljaju, redom, broj gradova i broj auto-puteva ( n ≤ 20.000, m≤ 200.000). U narednih m redova sledi opis mape: po tri broja a_i, b_i i c_i u svakom redu koji očnačavaju da postoji (neusmeren) put između gradova a_i i b_i, pri čemu je taj put asfaltiran ako je c_i = 0. Gradovi su numerisani od 1 do n i između svaka dva grada postoji najviše jedan auto-put.

Izlaz:

(Izlazni podaci se ispisuju u datoteku asfalt.out.) U prvom redu izlaza ispisati broj gradova koji su kandidati za glavni grad. U sledećem redu ispisati redne brojeve tih gradova u proizvoljnom redosledu,odvojene razmakom.

Primer:

4 4
1 2 1
2 3 1
3 4 1
4 1 0

2
2 3

Objašnjenje.

Asfaltirani putevi su: 1-2, 2-3 i 3-4. Ukoliko bi grad 1 bio glavni grad onda bi sused grada 4 koji ima najveću vrednost bio baš grad 1 i grad 4 bi asfaltirao put 4-1. Međutim, ovaj put nije asfaltiran pa grad 1 ne može biti glavni. Slično i za grad 4. Gradovi 2 i 3 mogu biti glavni, npr. za v(1) = 1, v(2) = 4, v(3) = 3 i v(4) = 2, grad 2 postaje glavni i asfaltiranje je korektno. Slično i za grad 3.

Napomena.

U 30% test primera je n≤ 200 a u 50% test primera n≤ 2.000.

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <memory.h>

using namespace std;

const int MaxN = 20200;
const int MaxM = 200200;

struct edge {
  int v;
  bool asfalt;
  edge(int x, bool y) { v = x; asfalt = y; }; 
};

int dfs[MaxN], currSon[MaxN], city[MaxN];
vector<edge> adj[MaxN];
bool mark[MaxN];
int n, m, time, root, sol, a, b, c;

void DFS(int u) {
  int v;

  time++;
  dfs[u] = time;

  for (int i = 0; i < adj[u].size(); i++) {
    v = adj[u][i].v;
    
    // ako je u-v tree-edge i cvor v nije obidjen
    if (adj[u][i].asfalt && dfs[v] == 0) {
      currSon[u] = v;
      DFS(v);
    }
    // ako u-v nije tree-edge i cvor v je vec obidjen
    if (!adj[u][i].asfalt && dfs[v] != 0) {

      //tada je u-v back ili "cross" edge i markiramo krajeve
      mark[u] = true;
      mark[v] = true;

      //ako je u-v back edge, proverimo da li nam treba novi root
      if (currSon[v] != 0 && dfs[ currSon[v] ] > dfs[root])
        root = currSon[v];
    }
  }

  currSon[u] = 0;
}

void DFS2(int u) {
  int v;

  mark[u] = true;
  city[sol++] = u;

  for (int i = 0; i < adj[u].size(); i++) {
    v = adj[u][i].v;
    if (adj[u][i].asfalt && !mark[v])
      DFS2(v);
  }
}

int main() {

  FILE* inFile = fopen("asfalt.in", "r");
  FILE* outFile = fopen("asfalt.out", "w");

  fscanf(inFile, "%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    fscanf(inFile, "%d%d%d", &a, &b, &c);
    adj[a].push_back(edge(b, c == 1));
    adj[b].push_back(edge(a, c == 1));
  }

  memset(dfs, 0, sizeof(dfs));
  memset(currSon, 0, sizeof(currSon));
  memset(mark, false, sizeof(mark));
  root = 1;  time = 0;  sol = 0;

  DFS(1);
  DFS2(root);

  fprintf(outFile, "%d\n", sol);
  for (int i = 0; i < sol - 1; i++)
    fprintf(outFile, "%d ", city[i]);
  fprintf(outFile, "%d\n", city[sol - 1]);

  return 0;
}

const
  MaxN = 20020;
  MaxM = 200020;


var
   inFile, outFile: Text;
   n, m, time, root, sol, a, b, c : longint;
   dfsNum, currSon, city, p, deg : array[0..MaxN] of longint;
   a1, b1, c1, adj, asfalt : array[0..2*MaxM] of longint;
   mark : array[0..MaxN] of boolean;



procedure Input;
var
   i, a, b, c: longint;

begin

   assign( inFile, 'asfalt.in' );
   reset( inFile );
   fillchar( deg, sizeof( deg ), 0 );

   readln( inFile, n, m );
   for i := 1 to m do begin
      readln( inFile, a, b, c );
      deg[ a ] := deg[ a ] + 1;
      deg[ b ] := deg[ b ] + 1;
      a1[ i ] := a; b1[ i ] := b; c1[ i ] := c;
      a1[ i + m ] := b; b1[ i + m ] := a; c1[ i + m] := c;
   end;

   close( inFile );

end;



procedure Output;
var
  i : longint;

begin

   assign( outFile, 'asfalt.out' );
   rewrite( outFile );
   writeln( outFile, sol );
   for i := 1 to sol - 1 do
      write( outFile, city[ i ], ' ' );
   writeln( outFile, city[ sol ] );
   close( outFile);

end;



(* simulacija liste preko counting sorta *)
procedure ListSimulation;
var
   i: longint;

begin

   p[0] := 0;
   for i := 1 to n do
      p[ i ] := p[ i - 1 ] + deg[ i - 1 ];

   for i := 1 to 2 * m do begin
      adj[ p[ a1[ i ] ] ] := b1[ i ];
      asfalt[ p[ a1[ i ] ] ] := c1[ i ];
      p[ a1[ i ] ] := p[ a1[ i ] ] + 1;
   end;

   for i := 1 to n do
      p[ i ] := p[ i - 1 ] + deg[ i - 1 ];

end;



procedure DFS( u : longint );
var
   v, i : longint;

begin

   time := time + 1;
   dfsNum[ u ] := time;

   for i := p[ u ] to p[ u ] + deg[ u ] - 1 do begin
      v := adj[ i ];


      (* ako je u-v tree-edge i cvor v nije obidjen *)
      if ( (asfalt[ i ] = 1) AND (dfsNum[ v ] = 0) ) then begin
         currSon[ u ] := v;
         DFS( V );
      end;

      (* ako u-v nije tree-edge i cvor v je vec obidjen *)
      if ( (asfalt[ i ] = 0) AND (dfsNum[ v ] <> 0) ) then begin

         (* tada je u-v back ili "cross" edge i markiramo krajeve *)
   mark[ u ] := true;
   mark[ v ] := true;

   (* ako je u-v back edge, proverimo da li nam treba novi root *)
   if ( (currSon[ v ] <> 0) AND (dfsNum[ currSon[ v ] ] > dfsNum[ root ]) ) then
      root := currSon[ v ];

      end;

   end;

   currSon[ u ] := 0;

end;



procedure DFS2( u : longint );
var
   v, i : longint;

begin

   mark[ u ] := true;
   sol := sol + 1;
   city[ sol ] := u;

   for i := p[ u ] to p[ u ] + deg[ u ] - 1 do begin
      v := adj[ i ];
      if ( (asfalt[ i ] = 1) AND (NOT mark[ v ]) ) then
         DFS2(v);
   end;

end;



begin

   Input;
   ListSimulation;

   fillchar( dfsNum, sizeof( dfsNum ), 0 );
   fillchar( currSon, sizeof( currSon ), 0);
   fillchar( mark, sizeof( mark ), false );
   root := 1;  time := 0;  sol := 0;

   DFS(1);
   DFS2(root);

   Output;

end.