#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 two packs of numbers.
template <typename, typename> struct Merge;

template <template <std::size_t...> class P1, template <std::size_t...> class P2, std::size_t... Is, std::size_t... Js>
struct Merge<P1<Is...>, P2<Js...>> {
	using type = P1<Is..., Js...>;
};

// Obtaining the last element from a pack.
template <typename, typename> struct LastType;

template <typename T, template <T...> class P, T Last>
struct LastType<T, P<Last>> : std::integral_constant<T, Last> {};

template <typename T, template <T...> class P, T First, T... Rest>
struct LastType<T, P<First, Rest...>> : LastType<T, P<Rest...>> {};

// 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 {};

// Checking if t of type T is a last child.  Using ExistsInPack will not work correctly here.
template <typename T, T t, T...> struct IsALastChild;

template <typename T, T t, T Child, T Parent, T... Rest>
struct IsALastChild<T, t, Child, Parent, Rest...> : IsALastChild<T, t, Rest...> {};  // Here is the difference with ExistsInPack.  We must skip the parent and check the next child (if any) because we don't want the child to be read as a parent.

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

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

// 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<>> {};

// Given Child, find its parent from the pack P<LastChildAndParent...>.
template <std::size_t Child, std::size_t First, std::size_t Second, std::size_t... Rest>
struct GetParent : GetParent<Child, Rest...> {};

template <std::size_t Child, std::size_t Parent, std::size_t... Rest>
struct GetParent<Child, Child, Parent, Rest...> : std::integral_constant<std::size_t, Parent> {};

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

// Given Child, remove Child and its parent from P<LastChildAndParent...>.
template <template <std::size_t...> class P, std::size_t Child, std::size_t First, std::size_t Second, std::size_t... Rest, std::size_t... Accumulated>
struct RemoveChildAndParentHelper<Child, P<First, Second, Rest...>, P<Accumulated...>> : RemoveChildAndParentHelper<Child, P<Rest...>, P<Accumulated..., First, Second>> {};

template <template <std::size_t...> class P, std::size_t Child, std::size_t Parent, std::size_t... Rest, std::size_t... Accumulated>
struct RemoveChildAndParentHelper<Child, P<Child, Parent, Rest...>, P<Accumulated...>> {
	using type = P<Accumulated..., Rest...>;
};

template <template <std::size_t...> class P, std::size_t Child, std::size_t... Accumulated>
struct RemoveChildAndParentHelper<Child, P<>, P<Accumulated...>> {
	using type = P<Accumulated...>;
};

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

template <template <std::size_t...> class P, std::size_t Child, std::size_t... LastChildAndParent>
struct RemoveChildAndParent<Child, P<LastChildAndParent...>> : RemoveChildAndParentHelper<Child, P<LastChildAndParent...>, 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<>;
};

// Removing duplicates from a pack.  This is only used for the alternate Graph class that allows using any values for its vertices (not necessarily consecutive).
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<>> {};

// 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, bool> struct CheckIfLastAdjacentVertex;

// 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 <template <std::size_t...> class P, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
struct TopologicalSort<P<>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> {
	using topological_sort = P<Vertices...>;  // The final stack of vertices describing a topological order.
};

// The topological sort loop.
template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>  // First, Rest... are the vertices to be visited now (in that order).
struct TopologicalSort<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> :
	TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited..., First>, P<LastChildAndParent...>, P<Vertices...>,  // Append First to P<Visited...>.
			typename RemoveThoseAlreadyVisited<std::size_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.

// First has adjacent edges, so visit its adjacent vertices, and prepend First to P<Vertices...> AFTER these visits.  To ensure this last part, add First and its last child into P<LastChildAndParent...>, and check later on when this last child of First is visited.  Note that since all vertices have UNIQUE std::size_t ID numbers, there will be no mix-up with other vertices when this last child is visited.
template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices, typename AdjacentVertices>
struct TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, AdjacentVertices> :
	CheckIfLastAdjacentVertex<typename Merge<AdjacentVertices, P<Rest...>>::type, P<Edges...>, P<Visited...>,  // Go into CheckIfLastAdjacentVertex, because it First is the last adjacent vertex of some parent vertex, that parent vertex shall be prepended to P<Vertices...> immediate after First is prepended to P<Vertices...>.
		P<LastChildAndParent..., LastType<std::size_t, AdjacentVertices>::value, First>, P<Vertices...>, IsALastChild<std::size_t, First, LastChildAndParent...>::value> {};

// First has no adjacent vertices, so prepend it to P<Vertices...>.  Here too, we must go into CheckIfLastAdjacentVertex in case First is the last adjacent vertex of some parent vertex.
template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
struct TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, P<>> :
	CheckIfLastAdjacentVertex<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<First, Vertices...>, IsALastChild<std::size_t, First, LastChildAndParent...>::value> {};

// First is the last adjacent vertex of some parent vertex, so prepend its parent vertex to P<Vertices...>.  Note that First cannot be mixed up with another vertex because all vertices in the Graph have UNIQUE values.
template <template <std::size_t...> class P, std::size_t First, std::size_t... Rest, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>
struct CheckIfLastAdjacentVertex<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, true> :  // First and its parent vertex must be removed from P<LastChildAndParent...> right now.
	TopologicalSort<typename RemoveThoseAlreadyVisited<std::size_t, P<Rest...>, P<Visited...>>::type, P<Edges...>, P<Visited...>,  // We MUST remove all vertices that have already been visited before going into TopologicalSort, since TopologicalSort always assumes First has not been visited before.
		typename RemoveChildAndParent<First, P<LastChildAndParent...>>::type, P<GetParent<First, LastChildAndParent...>::value, Vertices...>> {};  // Do NOT prepend First into P<Vertices...> because this was already done in TopologicalSortHelper<P<First, Rest...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, P<>>.
	
// First is not the last adjacent vertex of some parent vertex, so simply do the regular TopologicalSort (but removing the vertices already visited first, of course).
template <template <std::size_t...> class P, std::size_t... ToVisit, std::size_t... Visited, std::size_t... Edges, std::size_t... LastChildAndParent, std::size_t... Vertices>  // No need for First, Rest... here since First needs not be identified in this case.
struct CheckIfLastAdjacentVertex<P<ToVisit...>, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>, false> :
	TopologicalSort<typename RemoveThoseAlreadyVisited<std::size_t, P<ToVisit...>, P<Visited...>>::type, P<Edges...>, P<Visited...>, P<LastChildAndParent...>, P<Vertices...>> {};

template <std::size_t N, std::size_t... Edges>
struct Graph : TopologicalSort<make_index_sequence<N>, index_sequence<Edges...>, index_sequence<>, 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 = Graph<6, 5,2, 5,0, 4,0, 4,1, 2,3, 3,1>;
	DAG1::topological_sort::print();  // 5 4 2 3 1 0
	std::cout << std::boolalpha << std::is_same<DAG1::topological_sort, index_sequence<5,4,2,3,1,0>>::value << std::endl;  // true
	
	using DAG2 = Graph<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>;
	DAG2::topological_sort::print();  // 0 3 2 6 1 5 4 7
	std::cout << std::boolalpha << std::is_same<DAG2::topological_sort, index_sequence<0,3,2,6,1,5,4,7>>::value << std::endl;  // true
}