#include<iostream> #include<stdio.h> #include<vector> #include<stack> #include<algorithm> #include<queue> using namespace std ; #define MAXN 200007 int n , m , k ; int c[ MAXN ] ; vector < int > v[ MAXN ] ; vector < int > gr[ MAXN ] ; vector < int > rev[ MAXN ] ; int used[ MAXN ] ; stack < int > s ; vector < int > CompList[ MAXN ] ; int comp[ MAXN ] ; bool IsChosen[ MAXN ] ; bool FComp[ MAXN ] ; int br[ MAXN ] ; bool from[ MAXN ] ; int order[ MAXN ] ; int revorder[ MAXN ] ; int Mark[ 17 ][ 17 ] ; int SlowIds[ 17 ] ; bool cmp ( int x , int y ) { if ( IsChosen[ x ] != IsChosen[ y ] ) { return ( IsChosen[ x ] > IsChosen[ y ] ) ; } return ( x < y ) ; } void clear ( ) { int i , j ; while ( s.empty ( ) == false ) { s.pop ( ) ; } for ( i = 0 ; i < MAXN ; i ++ ) { c[ i ] = 0 ; v[ i ].clear ( ) ; gr[ i ].clear ( ) ; rev[ i ].clear ( ) ; used[ i ] = 0 ; CompList[ i ].clear ( ) ; comp[ i ] = 0 ; IsChosen[ i ] = false ; FComp[ i ] = false ; br[ i ] = 0 ; from[ i ] = false ; order[ i ] = 0 ; revorder[ i ] = 0 ; } if ( n <= 30 ) { for ( i = 1 ; i <= n ; i ++ ) { SlowIds[ i ] = 0 ; for ( j = 1 ; j <= n ; j ++ ) { Mark[ i ][ j ] = 0 ; } } } } void dfs ( int vertex ) { used[ vertex ] = 1 ; int i ; int sz = v[ vertex ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { if ( used[ v[ vertex ][ i ] ] == 0 ) { dfs ( v[ vertex ][ i ] ) ; } } s.push ( vertex ) ; } void rec ( int vertex ) { CompList[ comp[ vertex ] ].push_back ( vertex ) ; if ( IsChosen[ vertex ] == true ) { FComp[ comp[ vertex ] ] = true ; } int i ; int sz = rev[ vertex ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { int h = rev[ vertex ][ i ] ; if ( comp[ h ] == 0 ) { comp[ h ] = comp[ vertex ] ; rec ( h ) ; } } } void input ( ) { scanf ( "%d%d%d" , &n , &m , &k ) ; int i ; for ( i = 1 ; i <= k ; i ++ ) { scanf ( "%d" , &c[ i ] ) ; IsChosen[ c[ i ] ] = true ; } sort ( c + 1 , c + k + 1 ) ; int x , y ; for ( i = 1 ; i <= m ; i ++ ) { scanf ( "%d%d" , &x , &y ) ; v[ x ].push_back ( y ) ; rev[ y ].push_back ( x ) ; gr[ x ].push_back ( y ) ; } } bool check ( ) { int i ; for ( i = 1 ; i < k ; i ++ ) { if ( Mark[ c[ SlowIds[ i ] ] ][ c[ SlowIds[ i + 1 ] ] ] == 0 ) { return false ; } } for ( i = 1 ; i <= k ; i ++ ) { printf ( "%d" , c[ SlowIds[ i ] ] ) ; if ( i == k ) { printf ( "\n" ) ; } else { printf ( " " ) ; } } return true ; } void mark ( int vertex , int id ) { used[ vertex ] = 1 ; Mark[ id ][ vertex ] = 1 ; int i ; int sz = v[ vertex ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { if ( used[ v[ vertex ][ i ] ] == 0 ) { mark ( v[ vertex ][ i ] , id ) ; } } } void slow ( ) { int i , j ; for ( i = 1 ; i <= n ; i ++ ) { SlowIds[ i ] = i ; mark ( i , i ) ; for ( j = 1 ; j <= n ; j ++ ) { used[ j ] = 0 ; } } if ( check ( ) == true ) { return ; } while ( next_permutation ( SlowIds + 1 , SlowIds + k + 1 ) ) { if ( check ( ) == true ) { return ; } } printf ( "-1\n" ) ; } void solve ( ) { int i , j , t ; for ( i = 1 ; i <= n ; i ++ ) { if ( used[ i ] == 0 ) { dfs ( i ) ; } } int id = 1 ; while ( s.empty ( ) == false ) { int vertex = s.top ( ) ; s.pop ( ) ; if ( comp[ vertex ] != 0 ) { continue ; } comp[ vertex ] = id ; id ++ ; rec ( vertex ) ; } for ( i = 1 ; i <= n ; i ++ ) { used[ i ] = 0 ; v[ i ].clear ( ) ; } id -- ; /** for ( i = 1 ; i <= id ; i ++ ) { printf ( "--%d\n" , i ) ; for ( j = 0 ; j < CompList[ i ].size ( ) ; j ++ ) { printf ( "%d " , CompList[ i ][ j ] ) ; } printf ( "\n" ) ; } **/ for ( i = 1 ; i <= id ; i ++ ) { int sz1 = CompList[ i ].size ( ) ; for ( j = 0 ; j < sz1 ; j ++ ) { int cur = CompList[ i ][ j ] ; int sz2 = gr[ cur ].size ( ) ; for ( t = 0 ; t < sz2 ; t ++ ) { if ( used[ comp[ gr[ cur ][ t ] ] ] == 0 ) { if ( comp[ gr[ cur ][ t ] ] != i ) { v[ i ].push_back ( comp[ gr[ cur ][ t ] ] ) ; } used[ comp[ gr[ cur ][ t ] ] ] = 1 ; } } } for ( j = 0 ; j < sz1 ; j ++ ) { int cur = CompList[ i ][ j ] ; int sz2 = gr[ cur ].size ( ) ; for ( t = 0 ; t < sz2 ; t ++ ) { used[ comp[ gr[ cur ][ t ] ] ] = 0 ; } } } int jgh = 0 ; for ( i = 1 ; i <= id ; i ++ ) { if ( FComp[ i ] == true ) { jgh ++ ; } } if ( jgh == 1 ) { int tot = 0 ; for ( i = 1 ; i <= id ; i ++ ) { if ( FComp[ i ] == true ) { sort ( CompList[ i ].begin ( ) , CompList[ i ].end ( ) , cmp ) ; int sz = CompList[ i ].size ( ) ; for ( j = 0 ; j < sz ; j ++ ) { if ( IsChosen[ CompList[ i ][ j ] ] == false ) { break ; } tot ++ ; printf ( "%d" , CompList[ i ][ j ] ) ; if ( tot == k ) { printf ( "\n" ) ; } else { printf ( " " ) ; } } } } return ; } /** for ( i = 1 ; i <= id ; i ++ ) { printf ( "--%d\n" , i ) ; for ( j = 0 ; j < v[ i ].size ( ) ; j ++ ) { printf ( "%d " , v[ i ][ j ] ) ; } printf ( "\n" ) ; } **/ for ( i = 1 ; i <= id ; i ++ ) { int sz = v[ i ].size ( ) ; for ( j = 0 ; j < sz ; j ++ ) { br[ v[ i ][ j ] ] ++ ; } } queue < int > q ; for ( i = 1 ; i <= id ; i ++ ) { if ( br[ i ] == 0 ) { q.push ( i ) ; } } int st ; bool fl = false ; int tp = 1 ; while ( q.empty ( ) == false ) { st = q.front ( ) ; q.pop ( ) ; order[ st ] = tp ; revorder[ tp ] = st ; tp ++ ; if ( FComp[ st ] == true && fl == false ) { from[ st ] = true ; fl = true ; } int sz = v[ st ].size ( ) ; for ( i = 0 ; i < sz ; i ++ ) { int h = v[ st ][ i ] ; if ( br[ h ] == 0 ) { continue ; } br[ h ] -- ; if ( br[ h ] == 0 ) { q.push ( h ) ; if ( from[ st ] == true ) { from[ h ] = true ; } } } } for ( i = 1 ; i <= id ; i ++ ) { if ( FComp[ i ] == true && from[ i ] == false ) { printf ( "-1\n" ) ; return ; } } tp -- ; int tot = 0 ; for ( i = 1 ; i <= tp ; i ++ ) { if ( FComp[ revorder[ i ] ] == false ) { continue ; } int sz = CompList[ revorder[ i ] ].size ( ) ; sort ( CompList[ revorder[ i ] ].begin ( ) , CompList[ revorder[ i ] ].end ( ) , cmp ) ; for ( j = 0 ; j < sz ; j ++ ) { if ( IsChosen[ CompList[ revorder[ i ] ][ j ] ] ) { tot ++ ; printf ( "%d" , CompList[ revorder[ i ] ][ j ] ) ; if ( tot == k ) { printf ( "\n" ) ; } else { printf ( " " ) ; } } } } if ( tot == k ) { return ; } printf ( "-1\n" ) ; } int main ( ) { int t ; scanf ( "%d" , &t ) ; while ( t != 0 ) { t -- ; input ( ) ; if ( n <= 17 ) { slow ( ) ; } else { solve ( ) ; } clear ( ) ; } return 0 ; }