All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Micro and Challenge
Tag(s):

Medium

Problem
Editorial
Analytics

Micro just read an amazing article on Topological Sorting. He was so impressed by it, that he went to the Code shop, purchased a Directed Acyclic Graph, and started applying Topological Sort on it. He tried finding out total number of topological sorting possible, for its vertices. He successfully did that and called that number $$T$$. Now, he tried another challenge, but got stuck. The challenge is to find the $$K^{th}$$ lexicographically largest topological sorting of the vertices. Help Micro find this out.

Input:
First line consists of three space separated integers, $$N$$ - number of vertices, $$M$$ - number of edges and $$K$$ - as described in the question.
Each of the following $$M$$ lines contain two space separated integers $$X$$, and $$Y$$ denoting there is an from $$X$$ to $$Y$$.

Output:
Print $$N$$ space separated integers denoting the $$K^{th}$$ lexicographically largest topological sorting.

Constraints:
$$1 \le N \le 20$$
$$1 \le M \le 50$$
$$1 \le X, Y \le N$$
$$1 \le K \le T \le 10^{15}$$

SAMPLE INPUT
3 1 2
1 2
SAMPLE OUTPUT
1 3 2
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications