#include <iostream>
#include <type_traits>

template <std::size_t...> struct index_sequence {};

template <std::size_t N, std::size_t... Is>
struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence_helper<0, Is...> {
    using type = index_sequence<Is...>;
};

template <std::size_t N>
using make_index_sequence = typename make_index_sequence_helper<N>::type;

// Merging packs.
template <typename, typename...> struct Merge;

template <typename T, template <T...> class P1, template <T...> class P2, T... Is, T... Js>
struct Merge<T, P1<Is...>, P2<Js...>> {
	using type = P1<Is..., Js...>;
};

template <typename T, typename First, typename... Rest>
struct Merge<T, First, Rest...> : Merge<T, First, typename Merge<T, Rest...>::type> {};

// Checking if t of type T exists in a pack of T objects.
template <typename T, T t, T...> struct ExistsInPack;

template <typename T, T t, T First, T... Rest>
struct ExistsInPack<T, t, First, Rest...> : ExistsInPack<T, t, Rest...> {};

template <typename T, T t, T... Rest>
struct ExistsInPack<T, t, t, Rest...> : std::true_type {};

template <typename T, T t>
struct ExistsInPack<T, t> : std::false_type {};

// Removing duplicates from a pack.
template <typename, typename, typename> struct RemoveDuplicatesHelper;

template <typename T, template <T...> class P, T First, T... Rest, T... Accumulated>
struct RemoveDuplicatesHelper<T, P<First, Rest...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Accumulated..., Rest...>::value,
		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated...>>,
		RemoveDuplicatesHelper<T, P<Rest...>, P<Accumulated..., First>>
	>::type {};

template <typename T, template <T...> class P, T... Accumulated>
struct RemoveDuplicatesHelper<T, P<>, P<Accumulated...>> {
	using type = P<Accumulated...>;
};

template <typename, typename> struct RemoveDuplicates;

template <typename T, template <T...> class P, T... Ts>
struct RemoveDuplicates<T, P<Ts...>> : RemoveDuplicatesHelper<T, P<Ts...>, P<>> {};

// Obtaining the adjacent vertices of a given vertex.
template <std::size_t, typename, typename> struct AdjacentVerticesHelper;

template <std::size_t Vertex, template <std::size_t...> class P, std::size_t From, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
struct AdjacentVerticesHelper<Vertex, P<From, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated...>> {};

template <std::size_t Vertex, template <std::size_t...> class P, std::size_t To, std::size_t... RemainingPairs, std::size_t... Accumulated>
struct AdjacentVerticesHelper<Vertex, P<Vertex, To, RemainingPairs...>, P<Accumulated...>> : AdjacentVerticesHelper<Vertex, P<RemainingPairs...>, P<Accumulated..., To>> {};

template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Accumulated>
struct AdjacentVerticesHelper<Vertex, P<>, P<Accumulated...>> {
	using type = P<Accumulated...>;
	static const bool nonempty = sizeof...(Accumulated) > 0;
};

template <std::size_t, typename> struct AdjacentVertices;

template <std::size_t Vertex, template <std::size_t...> class P, std::size_t... Edges>
struct AdjacentVertices<Vertex, P<Edges...>> : AdjacentVerticesHelper<Vertex, P<Edges...>, P<>> {};

// Removing from a pack all the elements in P<Visited...>.
template <typename, typename, typename, typename> struct RemoveThoseAlreadyVisitedHelper;

template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Accumulated>
struct RemoveThoseAlreadyVisitedHelper<T, P<First, Rest...>, P<Visited...>, P<Accumulated...>> : std::conditional<ExistsInPack<T, First, Visited...>::value,
		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated...>>,
		RemoveThoseAlreadyVisitedHelper<T, P<Rest...>, P<Visited...>, P<Accumulated..., First>>
	>::type {};

template <typename T, template <T...> class P, T... Visited, T... Accumulated>
struct RemoveThoseAlreadyVisitedHelper<T, P<>, P<Visited...>, P<Accumulated...>> {
	using type = P<Accumulated...>;
};

template <typename, typename, typename> struct RemoveThoseAlreadyVisited;

template <typename T, template <T...> class P, T... Ts, T... Visited>
struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<Visited...>> : RemoveThoseAlreadyVisitedHelper<T, P<Ts...>, P<Visited...>, P<>> {};

template <typename T, template <T...> class P, T... Ts>
struct RemoveThoseAlreadyVisited<T, P<Ts...>, P<>> {  // These remaining specializations are to avoid using the above specialization since 'type' is immediately obvious and needs no computation.
	using type = P<Ts...>;
};

template <typename T, template <T...> class P, T... Visited>
struct RemoveThoseAlreadyVisited<T, P<>, P<Visited...>> {
	using type = P<>;
};

template <typename T, template <T...> class P>
struct RemoveThoseAlreadyVisited<T, P<>, P<>> {  // This is needed to avoid ambiguity with the above two specializations.
	using type = P<>;
};

// Now the main structs.
template <typename, typename, typename, typename, typename> struct TopologicalSort;
template <typename, typename, typename, typename, typename, typename> struct TopologicalSortHelper;
template <typename, typename, typename, typename, typename, typename> struct UpdateStack;
template <typename, typename, typename, typename, typename> struct ReturnToTopologicalSort;

// End of the topological sort loop.  Replacing P<Visited...> with typename Visited and/or P<Edges...> with typename Edges and/or P<Vertices...> with typename Stack will cause ambiguity compiling error since neither this nor the above partial specialization is more specialized than the other. 
template <typename T, template <T...> class P, T... Visited, T... Edges, T... Vertices>
struct TopologicalSort<T, P<>, P<Edges...>, P<Visited...>, P<Vertices...>> {
	using topological_sort = P<Vertices...>;  // The final stack of vertices describing a topological order.
	using visited = P<Visited...>;  // This is just to check that P<Visited...> does not have repeats (to ensure optimal performance).
};

// The topological sort loop.
template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices>  // First, Rest... are the vertices to be visited now (in that order).
struct TopologicalSort<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>> :
	TopologicalSortHelper<T, P<First, Rest...>, P<Edges...>, P<Visited..., First>, P<Vertices...>,  // Append First to P<Visited...>.
			typename RemoveThoseAlreadyVisited<T, typename AdjacentVertices<First, P<Edges...>>::type, P<Visited...>>::type> {};  // Pass the adjacent vertices of First (if any), except those that have already been visited.

// The first type in ToVisit... has adjacent edges, so visit its adjacent vertices, and prepend this first type to P<Vertices...> AFTER these visits.
template <typename T, template <T...> class P, T... ToVisit, T... Visited, T... Edges, T... Vertices, typename AdjacentVertices>
struct TopologicalSortHelper<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>, AdjacentVertices> :
	UpdateStack<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>, TopologicalSort<T, AdjacentVertices, P<Edges...>, P<Visited...>, P<>>> {};  // Must use P<> instead of P<Vertices...> here, because we are going to adjoin the topological_sort of this particular subtree to P<Vertices...>.

// First has no adjacent vertices, so prepend it to P<Vertices...>.  Simply prepend First to P<Vertices...>, and move on to Rest...
template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices>
struct TopologicalSortHelper<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>, P<>> : TopologicalSort<T, P<Rest...>, P<Edges...>, P<Visited...>, P<First, Vertices...>> {};

// Updating P<Vertices...> after all adjacent (unvisited) edges have been visited.
template <typename T, template <T...> class P, T First, T... Rest, T... Visited, T... Edges, T... Vertices, typename AdjacentEdgesTopologicalSort>
struct UpdateStack<T, P<First, Rest...>, P<Edges...>, P<Visited...>, P<Vertices...>, AdjacentEdgesTopologicalSort> :
	ReturnToTopologicalSort<T, P<Rest...>, P<Edges...>,
		typename RemoveDuplicates<T, typename Merge<T, P<Visited...>, typename AdjacentEdgesTopologicalSort::visited>::type>::type,  // RemoveDuplicates is actually not necessarily (the results are still correct without it), but without it the P<Visited...> will have many duplicates in general and thus lead to slower computation of RemoveThoseAlreadyVisited. 
		typename Merge<T, P<First>, typename AdjacentEdgesTopologicalSort::topological_sort, P<Vertices...>>::type  // Wrapping the merge result with RemoveDuplicates is apparently not necessary, as it is apparently mathematically impossible for there to be duplicates after this merge.
	> {};

// Return to TopologicalSort, but first remove from ToVisit... all those that are in Visited...
template <typename T, template <T...> class P, T... ToVisit, T... Visited, T... Edges, T... Vertices>
struct ReturnToTopologicalSort<T, P<ToVisit...>, P<Edges...>, P<Visited...>, P<Vertices...>> :
	TopologicalSort<T, typename RemoveThoseAlreadyVisited<T, P<ToVisit...>, P<Visited...>>::type, P<Edges...>, P<Visited...>, P<Vertices...>> {};  // RemoveThoseAlreadyVisited is absolutely necesary.

// Now the Graph classes themselves.
template <std::size_t N, std::size_t... Edges>
struct Graph1 : TopologicalSort<std::size_t, make_index_sequence<N>, index_sequence<Edges...>, index_sequence<>, index_sequence<>> {};

// Sorter class needed for class Graph2, where the vertices can be non-consecutive integers, and the number of vertices does not need to be specified.
template <std::size_t I, std::size_t J>
struct IntLessThan : std::conditional<(I < J), std::true_type, std::false_type>::type {};

template <std::size_t, typename> struct PrependInt;

template <std::size_t N, template <std::size_t...> class Z, std::size_t... Is>  
struct PrependInt<N, Z<Is...>> {  
	using type = Z<N, Is...>;  
};

template <template<std::size_t> class, typename> struct FilterInts;  

template <template<std::size_t> class F, template <std::size_t...> class Z, std::size_t I, std::size_t... Is>  
struct FilterInts<F, Z<I, Is...>> {
	using type = typename std::conditional<F<I>::value,
		typename PrependInt<I, typename FilterInts<F, Z<Is...>>::type>::type,
		typename FilterInts<F, Z<Is...>>::type
	>::type;  
};

template <template<std::size_t> class F, template <std::size_t...> class Z>  
struct FilterInts<F, Z<>> {  
	using type = Z<>;  
};  

template <typename, typename> struct MergeIntSequences;  

template <template <std::size_t...> class Z, std::size_t... Is, std::size_t... Js>  
struct MergeIntSequences<Z<Is...>, Z<Js...>> {  
	using type = Z<Is..., Js...>;
};

template <typename, template <std::size_t, std::size_t> class = IntLessThan> struct SortIntSequence;  

template <template <std::size_t...> class Z, std::size_t N, std::size_t... Is, template <std::size_t, std::size_t> class Comparator>  
struct SortIntSequence<Z<N, Is...>, Comparator> {  
	template<std::size_t I> struct less_than : std::integral_constant<bool, Comparator<I,N>::value> {};
	template <std::size_t I> struct more_than : std::integral_constant<bool, Comparator<N,I>::value || I == N> {};  
	using subsequence_less_than_N = typename FilterInts<less_than, Z<Is...>>::type;
	using subsequence_more_than_N = typename FilterInts<more_than, Z<Is...>>::type; 
	using type = typename MergeIntSequences<typename SortIntSequence<subsequence_less_than_N, Comparator>::type,  
		typename PrependInt<N, typename SortIntSequence<subsequence_more_than_N, Comparator>::type>::type 
	>::type;
};

template<template <std::size_t...> class Z, template <std::size_t, std::size_t> class Comparator>  
struct SortIntSequence<Z<>, Comparator> {  
	using type = Z<>;  
};

// Graph2 is more flexible than Graph1 because the vertices can be non-consecutive integers, and the number of vertices does not need to be specified since that can be deduced by the vertices.
template <std::size_t... Edges>
struct Graph2 : TopologicalSort<std::size_t, typename SortIntSequence<typename RemoveDuplicates<std::size_t, index_sequence<Edges...>>::type>::type,  // All duplicates removed, and the vertices MUST be sorted for this to compile (though I didn't bother tracing why).  Of course, the vertices in Graph1 are already sorted.
	index_sequence<Edges...>, index_sequence<>, index_sequence<>> {};

// -------------------------- Testing --------------------------
template <std::size_t Last>
struct index_sequence<Last> {
    static void print() {std::cout << Last << std::endl;}
};

template <std::size_t First, std::size_t... Rest>
struct index_sequence<First, Rest...> {
    static void print() {std::cout << First << ' ';  index_sequence<Rest...>::print();}
};

int main() {
	using DAG1 = Graph1<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>;
	std::cout << "Topological sort of DAG1:  ";  DAG1::topological_sort::print();  // 5 4 2 3 1 0  (identical to the run-time solution at the top)
	std::cout << "Vertices visited in DAG1:  ";  DAG1::visited::print();  // 1 2 3 4 5 (no repeats)
	std::cout << std::boolalpha << std::is_same<DAG1::topological_sort, index_sequence<5,4,2,3,1,0>>::value << std::endl;  // true

	using DAG2 = Graph1<8, 0,1, 0,2, 0,3, 1,4, 1,5, 2,4, 2,6, 3,5, 3,6, 4,7, 5,7, 6,7>;
	std::cout << "\nTopological sort of DAG2:  ";  DAG2::topological_sort::print();  // 0 3 2 6 1 5 4 7  (identical to the run-time solution at the top)
	std::cout << "Vertices visited in DAG2:  ";  DAG2::visited::print();  // 0 1 4 7 5 2 6 3 (no repeats)
	std::cout << std::is_same<DAG2::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true

	using DAG3 = Graph1<8, 5,1, 1,2, 1,0, 1,6, 7,1, 7,4, 4,6, 3,0, 3,4>;  // This has the same edges as DAG5, with 11 renamed to 1, 10 renamed to 0, 9 renamed to 6, and 8 renamed to 4.
	std::cout << "\nTopological sort of DAG3:  ";  DAG3::topological_sort::print();  // 7 5 3 4 1 6 2 0  (identical to the run-time solution at the top)
	std::cout << "Vertices visited in DAG3:  ";  DAG3::visited::print();  // 0 1 2 6 3 4 5 7 (no repeats)
	std::cout << std::is_same<DAG3::topological_sort, index_sequence<7,5,3,4,1,6,2,0>>::value << std::endl;  // true

	std::cout << "\n\nUsing Graph2:" << std::endl;
	using DAG4 = Graph2<0,1, 0,2, 0,3, 1,4, 1,5, 2,4, 2,6, 3,5, 3,6, 4,7, 5,7, 6,7>;
	DAG4::topological_sort::print();  // 0 3 2 6 1 5 4 7  (same solution as DAG2 using the Graph1 class)
	std::cout << std::is_same<DAG4::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true

	using DAG5 = Graph2<5,11, 11,2, 11,10, 11,9, 7,11, 7,8, 8,9, 3,10, 3,8>;  // See the first diagram in http://e...content-available-to-author-only...a.org/wiki/Directed_acyclic_graph for a picture of this graph.
	DAG5::topological_sort::print();  // 7 5 11 3 8 9 10 2  (this is indeed a valid topological sort)

	using DAG6 = Graph2<5,1, 1,2, 1,0, 1,6, 7,1, 7,4, 4,6, 3,0, 3,4>;  // This Graph2 type has the same edges as DAG5, with 11 renamed to 1, 10 renamed to 0, 9 renamed to 6, and 8 renamed to 4.
	DAG6::topological_sort::print();  // 7 5 3 4 1 6 2 0  (identical to the run-time solution at the top)
	std::cout << std::is_same<DAG6::topological_sort, index_sequence<7,5,3,4,1,6,2,0>>::value << std::endl;  // true
}