RoAlgo Contest #4 (incepatori) | leximin

This was the problem page during the contest. Access the current page here.
Time limit: 2s Memory limit: 128MB Input: Output:

Given NN, MM, KK, and a directed acyclic graph (DAG) consisting of NN nodes (numbered from 11 to NN) and MM edges. Find the lexicographically smallest path that ends at node KK.

A sequence a1 a2  apa_1 \ a_2 \ \dots \ a_p is lexicographically smaller than sequence b1 b2  bqb_1 \ b_2 \ \dots \ b_q if and only if:

  1. p<qp < q and a1=b1a_1 = b_1, a2=b2a_2 = b_2, ap=bp\dots a_p = b_p or
  2. There exists a position pospos such that 1posmin(p,q)1 \leq pos \leq min(p, q) and a1=b1a_1 = b_1, a2=b2a_2 = b_2, \dots, apos1=bpos1a_{pos-1} = b_{pos-1}, and apos<bposa_{pos} < b_{pos}.

Input data

The first line contains three natural numbers, NN, MM, and KK, representing the number of nodes, the number of edges, and the node where the path will end. The next MM lines contain two numbers each, uu and vv, indicating that there is an edge from node uu to node vv.

Output data

The first line contains the number LL, representing the length of the lexicographically smallest path. The second line contains a sequence of length LL, representing the lexicographically smallest path.

Constraints and clarifications

  • 1N,M500 0001 \leq N, M \leq 500 \ 000
  • 1u,vN1 \leq u, v \leq N, uvu \neq v for each edge

Example 1

stdin

9 11 6
4 1
6 9
5 3
3 9
1 5
3 6
2 9
8 9
4 8
7 8
7 4

stdout

4
1 5 3 6

Log in or sign up to be able to send submissions!