#include <bits/stdc++.h>
using namespace std;
/*
Coded by 秦惜梦
The most attractive girl in the world
.........   `;!!!!!!!!!;;;;;;;;::::::'''''''``''''''''````````````````````....`:;;;;;:'.....`:|$$$$$$$|;;;:`.    ..........`''``...`''``.   ........   ...  ...   ....  ...   ...  '
........     '!!!!!!!!!;;;;;;;:::::::::''''':::''''`````````````````````......`:;;;;;!%$$%!'.....`:|$%!;;;'....   .....`....`'''`...```..    ........  ..   ...    ..   ...  ...   '
........     .:!!!!!!!!;;;;;;;:::::::::::::::'''''''`````````..```````........`:;!%$$$$$$$$$$$%!'.....`:|!'````..   .........`''``.......    ........  ...  ...   ...   ..   ..   .'
.......       `;!!!!!!;;;;;;;;::::::::::::::::'''''```````````.``````...       .`';|%$$$$$&&$$$$$$%%;'..`'':'''``..  ...``.....```.   ....    .......  ...  ...   ...  ...  ...   .'
.......      . '!!!!!!;;;;;;;:::'''''''''::::::'''```````````````````.........':'`.......`:!%%|||%$$$$$&%;'::::''``.   .```..   ....   ....   .......   ..  ...   ..   ...  ...  ..'
......      '::'''':::::::::::::'''''''''''::::''''``````````````````.........'!$$$$$$%!:`.......`:!%&&&|'``':::'''``.....```.   ....   ...    ......   .......   ..   ..  ...   ..'
``...       .`.``'::::::::;;;;:::::'''''''`'''''`````````````..```````........'!$$$$$$$$$$$$$$%!;'`.....`'`..`'::''''`.....```..  ....   ...   ......   ........ .... .......  ....'
````.      .````.`;!!!;;;;;;;;::'''''''``'''''`````````````````````````.. ....`:!|%$$$&&&&&&&$%%$&&&&@&$|::'`.`''''''''`....````.  ....   ...   ......   .  .....```..``.....  ... '
````      .````.  `;!!;;;;;;;:::::'''''':::'''''````````````........`````.... ........````........``'::::::::'``.``'''''``...````.. ....   ...  ......   .  ......``.```....   ..  '
```.      .```.  .`';!!;;;;;;;:::::::::::::'''''``````````..........````````...`;$$$$&&&&&&$%%||||!|!;;::::::::'`...`'''''`....````.  .... ...   .....   .   .. .``..```....  ..   '
``.       .``.  .`'`';!;;;;;;;;:::::::::::'''''`````````...........`````````....'!|%%%%%%%%%%%%%%%%%%$&&&|:'''''''`...`'''''`....```.  .... ...   .....  .   ..  ..  ......   .   .'
`.        .`.  `''''`';!;;;;;;;::::::::::'''''''```````..........````````````....:|%%%%%%%%%%%%%%%%%%%%%%|:`''''''''`...`''''`....```.. ...   ..  .....  ..  .   ..  .. ...  ..  ..'
`         .  .`'''''``';!;;;;;;;:::::::''''''''''```.``........```````````````````!%%%%%%%%%%||!;:''`.........`'''''''`...`''''`...````.....  ..   ....  ..  .   .   .  ..  ..  ...'
            .''''''````';!;;;;;;;:::::'''''''''''```````````````````````````.........``````...  ...```':;!!:....`'''''''``..`'''`....```.  ... ..  ....      ..  .   .  ..  ..  ...'
         .`''''''''``````;!;;;;;;:::::'''''''''''``````````'''''''''``....```````````````````````````':!||%|;``....`''''''``..`''``....`..  ...     ...   .  .   .  .. ..  .   ... '
        .'''''''''````````:;;;;:::'''''':::::::::::::''''''''''''``..``````....```````````````````````````:!!'`'`.....`'''''``...```.  .........    ....     .  ..  .  .  ..  ...  '
        `'''''''''````';;;:::::::::::::::::::::::''''```````````..........```````````````````````````````````'`.``'``....`''''``.. .`.. ..... ...    ...        .  .. ..  .   ..   '
       .'''''''''```````';;:::::''''''''''''''''''`''```````.`````.....````````````````````````````````''``````....``''`...``''```......  ........   ...     .     .  .  .   ..    '
       `''''''''````'''`````.`::::::::'''''''''''''''''``.``.```........````````````''''`````````````````''''''''`....``'``...``````...... ........   ..     .  .  . .   .  ..     '
      .`'''''''```'''''````````':::::::''''''''''''''``.``.`............`````````'''''''''''''''``````````'''''''''`.....````....```...  ..  ......    .                .   .     .'
      `'''''''`''''''''````````.`::::::'''''''''''''`.```..............``````````'''''''''''''''''````````''''''''''``.......```.........  .  ....     .     ........              '
     .`''''''`''''''''``````````.`:::::::'''''''''``.`..............```````'''''''''''''''''''''''''``````'''''''''''''.........``... .....  .  ...     ..`:::::::::::::'`.        '
      .'''''`''''''''``````````````':::::''''''''``..````````````````````''''''''''''''''''':''''''```''````''''::''''''`.```..........  .....   ....    `'::::::::::::::::`.      '
     ....`''''''''''```````````````.`':::::'''''`...``````````''''''''''''''''''''''''''''''';:'''``''`::````';:''''''''''.....``......... .....   ...   `::::::::::::::::::'`.....'
    ......`''''''''``````````````````.':::::::'`...``'''````''''''''''''''''''''''''''''''';!:;:'''':!;::'```````''''''''''`   ........ ..... ...    ..  ....`':::':::::::::::'... '
    .......`'''''`````````````````````.`':::'```.`''''''````''''''''':'''::'''::''':;::!!!;:;!;;:```````::`````````'''''''''`.     ............  ..   ..          .':::::::::''`   '
   ........`''`````````````````````````..`':''`:;:'':''':''''''''''''::'':;:'''''''''::'''''':;;;:``````:;'```''``````'``'''''`.... ...........    ..                 `::::::'`.   '
  ..........`````````````````````````'::::''':;!!!!;:'::':!;;;:::'''';;'''::::''''':'''::'''''''::'`````':''``''````::`':'''''''''.         ......                      .''`....   '
.`'`.......```````````````````````````````'':!;:::::::::':;::::::::''::''`''::::'`''''':::'':''`:;'`````':'```''`````::`````'''''':;'..................                 .......  . '
`'''''```````````````````````````````````.`;!:::::::::::'''::::::::''::''``'::::'``'''''::''''''':'````````````'`````''````````````:!!;'................              ..........   '
'''''`````````````````````````````````````;!;;;:':::''::''''::::;;:'':::'```'::'````''''''''''''':'```````````''````````````````````';!!!;'....  ......               .......      '
''''````````````````````````````````````';!;;;:'::::':''`''':::;;;:'''':'``'':'````.```''''''''`':'````````````'`````````..``....`...`:!!!!:`.`.....                    .          '
'''````````````````````````````````````':;!;;:`'::':'''``''':::;;;:''``'```'':'``....''`'''''''`''`.`````````````.````````.............';;'.`:;;;'`.                 .....   ...   '
''````````````````````````````````````'':!;::'`::':::''`''''':;;;;:```````'''''```...''`'''''''`''`.``.````````````````````............... `;;;;;;;;;:`.                ....   ....'
''''''''````````````````````````````''`:!;;:''':''::''`'':''':;;;;'```'```''''''`.`'``:'''::''''''```````````````````````````.............`:;;;;;;;;;;;'.      .         ....    ..'
:::::::''''````````````````````````''`'!!;:''''''':''`''''''':;;;:```::``'''':'''`';:';:'::::':`''`''`````````````````'``````````..........`:;;;;;;;;;:.     `'..          .....   '
|%$$%%!;;:'''````````````````````''``';!;:'''':'``'''`'':''':::;:'``:!:``':::::::`:!;';;':::::''`''::````'''''````````''`````````...........`:;;;;;;;'.    .':` `;;;;:. ..   ..... '
@@@@@@@@$|;:''`````````````````''```';!;:::::::'``````'':''::::::'`'!|:`':::;:::'';|!:;;'''''''::::;:``'::''`'````````''````````````.........`:;;;;;`     .:;'..';;;;;;;;;:` ......'
@@@@@@@@@@$|;:''`````````````:'`````;;;:';;;;::'`'````'':''::::::'`;!!;':::::::'`.';!;;;:::::';!!::;'`':::'``'`.``````''````````.......... ..``';;:`     .';;` `:;;;;;;;;;:` `;;;;;;
@@@@@@@@@@@&|;:'``````````''```````;;::':;;;;:'`''```'':'::::;;;:':;|!!;:'''''::::!||!!!!;!!!!||;:!'`:::::'````..``````''`````.......... .  ..`':;`     .';;:` ';;;;;;;;;;:. ';;;;;;
@@@@@@@@@@#@$!:''`````````````````::```';;;;::``'''``'::':::;;;::;;!|||!::;;!!!;;;:'``````'':!!!!|:``':::'`````:;:`.``````.............   . ..`';'     .';;;'..:;;;;;;;;;;'..';;;;;;
@@@@@@@@@@@@$|;:'````````````````::````:;;;::'.`''```''''':::;:::;||%|||%%%%%|!:''''`...`'':!;:;|;```:::'``''`';!;'..`````..............  . ..`''.    .';;;:` `;;;;;;;;;;;' .:;;;;;;
@@@@@@@@@@@&%!;:'```````````````''````':;;;::'..''```````:::::';||%%%%%%$$&&&%!;!|$&%:..';!%%!!|!'`;::::'``''';!;;'...````..............  ....``..   .';;;;'..';;;;;;;;;;;` `:;;;;;;
@@@@@@@@@#@%!!;:'````````````````````.'''::::`..````'''::!||||%%%%&&&&&&&&&&&&&$&&&%||||!|%%%%|!:';;;;!;``''`:;;;:`....`...................`....```. .`':::` `:;;;;;;;;;;:` `;;;;;;;
@@@@@@##@$|!!;:''```````````````````````':'```..`````':!;:''''':!%$&&&&&&&&&&&&$$$|!;;!|%%%%%%|;':;''::'`'''`:!;:`........................```..````........  .':;;;;;;;;;'. ';;;;;;;
!%$$$$%%|!!!;:''``````````````````````````````````````';!:'::'``':|$&&&&&&&&&&&&$$$$$$$$%%%%%|!:```''::'''''```...........................``..`'''`........   ......'::;;'..';;;;;;;
;!!!!!!!!!!;:''``````````````````````````````..````````'!%!;!;;!!%$%$&&&&&&&&&&&&$$$$$$$$$$%%||;``'''':''''``..`....    ... .................`'''````.....   .....`.......  `::;;;;;
::;!!!!!;;:''````````````````````````````````...````````'!%|!|%$$$$%$&&&&&&&&&&&&&&$$$$$$$$%|||:``''''''''```..`....      ..    ...     ....`'''`''```....   .'|%%;......    .... .'
``'::::'''````````````````````````````````````..`...```'`'|&$$$$$$$%$&&&&&&&&&&&&&&$$$$$$$$%%%|:`'''''''''```..`....                    ....`''```''```... .:%%%%|:......   .......'
 .````````````````````````````````````````````.``..```````:|&$$$$$$|%$&&&&&&&&&&&&&&&&&$$$$%%%|:'`'''''''````..`....                      .``'`````''````. :%%%%%;`....... ........'
  .``````````````````````````````````````````..`..`````````:%&&&&&&$%|%$&&&&&&&&&&&&&&&&$$$%$%|:'`'''''''````.``.....                    .``'`````'`'':|:.'!%%%%|'.`````.   .......'
  .```````````````````````````````````````````'`..`````````.:$&&&&&&&&&&&&&&&&&&&&&&&&&&&$$$$%|;'```''''```````.......                  .``'```'``':|%%|'.'|%%%%;```````...........'
  .`````````````````````````````````````````:'`..''````````..!&&&&&&&&&&&&&&&&&&&&&&&&&&&$$&$%%;''```''````````....   .                .'''`.`'``'`;%%%;``;%%$%!'..................'
  .``````````````````````````````````````;|:.``.`''''`````...`|&&&&&&&&&&&&&&&&&&&&&&&&&&$$&&$%!:'```````````.``..                    .`''```;;'''';%%%:.:%&&$|:...................:
  .```````````````````````````````````'!!```'`.`:!:''`````. ..`|&&&&&&&&&&&$%%$$$%|%$$&&&$$&&&$%;'`.``..`......`.                   ..`''''!;''''':|%$|'`!&&$|:...................`:
   .````````````````````````````````;|:````'::`'!;::''''`.  ...`!&&&&&&&&&&&&&&$&&&&&&&&&&$&&&&$|:'```.``.........        .`.    ....`'''```''''';$&&&;`:!;`......................`:
   .`````````````````````````````:|;`````'';:'`';:'''```.. ......'|&&&&&&&&&&&%%%$&&&&&&&$$&&&&&%;'`'`..```........         ``  `;:`''''``'```'!$&&&%!'.....................```````:
   .``````````````````````````:|;``````'':;:'``':'''`````. ........`:%&&&&&&&&&&&&&&&&&&&$&&&&|!!!;'''`....``......`.        .;%%;`''''';|||!;:''::;;' ..``......``````````````````:
   .```````````````````````!%:````````'':;:'```'':''````.. ............'|&@&&&&&&&&&&&&&&&$$|;!!!!!;:'``'`....``...````..      `:;;:'''!%;::::::::;;`. .````````'''````````````````:
   .```````````````````:%!'``````````'::::'````'''''````.  .............```;$&@&&&&&&&&&&$|;;!!!!!!!!;```::`  ...``.';;'```.    `:::'';$$|;:::::!;'`....``````''''''''````''''`````:
   .```````````````:%|'`````````````'::::'`````'''''''``.  .....  ....`````````;$&&&&@&|::!!;!!!!!!!!|!'```';'..  ....'!%%|!::``'':'':|$&&$|!!;:;:'`. .```````':::::''''''''''''''':
   .``````````;||:```````````````''::'::'````.`'''''''`.. .......  ..`````````````';:`````';!!!!!!!||||!;'```';!:`... ..`:|%%!'''''`:!%$&&&$$$!:;;;:'``'```''::::::::''''':::::'''';
   ..``';;:'```````````````````'''::'':'```````'''::''`..  .......   ..``````````````````. '||!!!|||||||!!;'````'!|;'``````````'''`';:'`'%&&&&&&|;!;:;!!!;;::;;::::::''''::::::::::;
``...``````````````````````''''''::''''`````````':::''``. .........  ....```````````...   .:!||||||%%%|||!!!!;'````'!||;'```.`'''`.`.`''`.;$&&&$:  .``'::::;!|%$$%|;:''':::::::::::;
    .````````````````````'''''''::```'````````.`:::'''```. .......... .............    `!%|!!||||%%||||!!!!!|%%%!:````````..`'''..``''`.....':. .   ..`':;;;;;;;::::;!%&%!;;;;:::::;
    .`````````````````''''''''''''''::'''````..`::''''`````. ........``............ .;%%%|!!!||%%%%%%%|!!!|%%%%%%||%%%%%%!'`'''`````....``.....       ..  .`':;;;;;;:::::;!%%!;;;;;;
    .`````````````'''''''''''```''''::'''''``..`''''''```````........````````.....:%%%$%||!|||%%%%%%%||!|%%%%%%%%%%%%|||!'`'''';%%|;`````......'`.      ..      `':::::::;;;;;|%!;;;
    .``````````''''''''''```````'```''''````..`.`'''''````````....  ..```....  `|%%%%$%|||!|%%%%%%%%%|!|%%%%%%%%%%%%%%%|:`'''`;%%%%!:.:!|%$$$$|;:'`...   .``..  .`.  '::::;;;;;;!%!;
%!'..```````''''''''''``````````'```'````````.``.`'''''```````.......       .;%%%%%%%|!!!||%%%%%|!!!!!|%%%%%%%%%%%%%%%%:`''''!%%%!!!:`:!|%$$$$$$$$$%|'`.  .```'`.``.  ..     .':::|%
%%%%%%;```''''''''```````````````'``''``````.````.`''''`..'````.......`'''';|%%%%%%%%||%%%%%%%%%%%|!!%%%%%%%%%%%%%%%%%:`'''';%%||||:`:!|%$$$$$$$$$$$$$%;``. .``''`.                '
$$$%%%%%$$|:''````````````````````''''``````.`````.`'''''`...      .`':|%$$%%%%%%%%%|!|%%%%%%%%%%|||%%$$%%%%%%%%%%%%%:`'''';%||%%%;.:||%$$$$$$$$$$$$$$&&&%:...````''`              '
$$$$$$$$$$%%%%%;`.``````````````````':'``````.`````.`'''''`......`''':!%%%%%%%%%%%%|!!%%%%|||%%|!|%%%%%%%%%%%%%%%%%%:`'''';||%%%|:`;||%$$$$$$$$$$$$&&&&&&&$|'...```'''`            '
|%%$$%%$$$$$%%%%%%%;`..`.`````````````':'````.``.```..`''````''''':|!:|%%%%%%%%%%%%|!!|%|||%||!!%%%%%%%%%%%%%%%%%%%:`'''':|%%%%;``;|%%$$$$$$$$$$&&&&&&&&&&&$$;...`````''`          '
@$|||||%%%%%%%%%%%%%%%%|:`....```````.`''``'''`````````.````''':;|%|;:|%%%%%%%%%%||!!|||||||!!|%%%%%%%%%%%%%%%%%%%:`'''';|%%%%:.'!|%$$$$$$$$$$$$$&&&&&&&&&&&&$!`..``````''`        '
||||&@&%|!|||%%%%%%%%%%%%%%|:.....```````'````.........`!%%%%%%%%|||;:|%%%%%%%%%%||!!|%|%|!!||%%%%%%%%%%%%%%%%%%%:`'''';|%%%!'`;||%$$$$$$$&&$$$$$&&&&&&@&&&&&$$!`..``````````.     '
|||||!|!|$@&%|!|||%%%%%%%%%%%%%:. ...`````''``........:|%%%%%%%%%||%;:|%%%%%%%$%%%%!;|||!!||||%%%%%%%%%%%%%%%%%%:`'''';||%|:`:||%%$$$&&&&&$$%%$$&&&&@######&&$$$!`..``..```````.   '
||||||||!|!!!!|%$%|||||%$%%%%%%%%%!`.....````'`......'|%%%%%%%%%%|%$|;%&&&&&&&&$$$$|!|!!%$$$$&&&&&&&&&$$$$$$$$%;`''':;|||;``;||%$$&&&&&&&$$%%$$&&&&&@######&$$$$%:.....``````````. '
||%%||||||!!|!!|||!|%$%|||%%%%%%%%%%%|:.....`.`'`...'|%%%%%%%%%$$$$&|:|&&&&&&&&$$$$|;!|$$$$&&&&&&&&&&&&&&&&@&$;`''':;||;``!||%$&$$$&&&&$%%%%%$&#####@@###@&$$&$$$!`.......`````````:
   .:!|%%|||||||||||||||!|||||%%%%$%%%%%;`.......``:%&&&&&&&&&&&&$$$%;;$&&&&&&&&&&$||$$$&&@@@@@@@@@@@@@@@@@@&!'''':;!:`'!||%$&$$$$$&&&$%%|%%$@######@&&&&&$$$$$$$%;..`...`...`````':
    .....`;|%%%%%|||!|||!|||!!!||%%%%%%%%%%;`.....:%&&&&&&&&&&&&$$$&$|'!$&&&&&&&$$%$$$&&@@@@@@@@@@@@@@@@@@@@!'::':'`.'|||%$$&&$$$$$&&$%%||%$@#########@@&&$$$$&$%$!`..`...```..````:
    ..........'!|%|%|||||!||||||||||%%%%%%%%%:...'|&&&&&&&&&&&&&$$&&&$;'|&&&&&$%%$$$&&@@@@@@@@@@@@@@@@@##@@!'::::'`:|%%%$$$&&&$$$$$$$%%|%&@@##########@@@@&&&$$$$$%;..``....````.``:
    .....```......`;|%|%%||||||||||||||%%%%%%|!:`!&&&&&&&&&&&&&&$$$&&$%::%&$$%%$$&&&@@@@@@@@@@@@@@@@@@@#@&|::::::;|%%$$$$&&&&&$$$$$$%%%%&@@@###########@@@@&&&&&$$$!`..`.....`````.'
    ..................`;|%%%|%%|||!|||||||%%%|||$&&&&&&&&&&&@&&&$$$&&&$%;;%%%$$&&@@@@@@@@@@@@@@@@@##@#@&$;':::::!%%$$$$&&&&&&&$$$%%%%%|$@@@@##@#########@@@@@&&&&$$|:...`.....`````:
    ............``..```...`;|%|||%||!!|||||||||%&&&&&&&&&&@@@@&&$$$&&&&$%;;%$$&@@@@@@@@@@@@@@@@@@#@@&$!`.`:::::!%$$$&&&&&&&&$$$$$$%%%||&@@@@##@@@@########@@@@&&&&$$!`...`.....````:
    ...................```...`:|%||||||||!||||%&&&&&&&&&&&@@@@@&$%&&$$$%%%;:!$&@@@@@@@@@@@@@@#@@&&%;``;|;:::::!$$$&&&&&&&&&&$$$$$%%%%||&@@@@@@@@@@##@#####@@@@@&&&&&$:..```.....```:
    .....................``.`...`;|%|||||||||%&&&&&&&&&&&&@@@@@@$$&$$%%$$$%!::|&@@@@@####@@@&$%;'':|%|!::::::!$$&&&&&@&&&&&&$$$$$$%%|||$@@@@@@@@@@@@@@@####@@@@@&&&&&%'.```..`...``:
    ...........................``..'!%|||||!%$&&&&&&&&&&&&@@@@@&$$$%%$$@@@&$%!::|&&&&&&&&$|;::;||||%%|::::::!$$&&&&@@@&&&&&&$$$$$$%%|||$@@@@&&&&&&&@@@@@@@@@@@@@@&&&$$|'.```.......:
    ...........................```...`;||||%$&&&&&&&&&&&&@@@@@&$%%$$&@@@@&&&&$|!!;;!||;:;!|%%||%$&&$|;:::::!$$&&&@@@@@@@&&&&$$$$$$%%%%|%&@@@&&&&&&&&&&&&&&&&&@@@&&&&$$$!`.``.......:
*/
#define jt const
#define ak int
#define ioi Mod=
#define times -999999993

int n,m,k;
vector<int> nei[55];
jt ak ioi 2000000000 times;
int C[205][205];

/*
   对于每一个双连通分量
   1.如果边数<点数，则可以放任意颜色。
   2.如果边数=点数，说明有且仅有1个环，则可以根据Burnside定理计算。
   3.如果边数>点数，说明有不止1个环，则两种方案如果所含每一种颜色的个数相同，一定可以通过变换使其完全相同。
*/

inline int ksmii(int a,int b){
	if(!b){
		return 1;
	}
	int x=ksmii(a,b>>1);
	x=1LL*x*x%Mod;
	if(b&1){
		x=1LL*x*a%Mod;
	}
	return x;
}

inline int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}

inline int burnside(int x){
	int ans=0;
	for(int i=1;i<=x;i++){
		ans=(ans+ksmii(k,gcd(i,x)))%Mod;
	}
	return 1LL*ans*ksmii(x,Mod-2)%Mod;
}

int dfn[55],tmc;
int low[55];
stack<int> stk;
int ans=1;

void tarjan(int now,int fa=0){
	low[now]=dfn[now]=++tmc;
	stk.push(now);
	for(int i:nei[now]){
		if(i==fa){
			continue;
		}
		if(!dfn[i]){
			tarjan(i,now);
			low[now]=min(low[now],low[i]);
			if(low[i]>=dfn[now]){
				set<int> hv;
				int cntv=0,cnte=0,xx;
				do{
					xx=stk.top();
					stk.pop();
					hv.insert(xx);
					cntv++;
				}while(xx!=i);
				hv.insert(now);
				cntv++;
				for(int i:hv){
					for(int j:nei[i]){
						if(hv.count(j)){
							cnte++;
						}
					}
				}
				cnte>>=1;
				if(cnte<cntv){
					ans=1LL*ans*k%Mod;
				}else if(cnte==cntv){
					ans=1LL*ans*burnside(cnte)%Mod;
				}else{
					ans=1LL*ans*C[cnte+k-1][k-1]%Mod;
				}
			}
		}else{
			low[now]=min(low[now],dfn[i]);
		}
	}
	if(!fa){
		stk.pop();
	}
}

int main(){
	for(int i=0;i<205;i++){
		C[i][0]=1;
	}
	for(int i=1;i<205;i++){
		for(int j=1;j<=i;j++){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
		}
	}
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		nei[a].push_back(b);
		nei[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 636