7577

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010, M = 200010,INF = 0x3f3f3f3f;
int p[N];
int n,m;

struct Edge{
int a,b,w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edge[M];

int find(int a){
if(p[a] != a)p[a] = find(p[a]);
return p[a];
}

int kru(){
sort(edge,edge + m);
for(int i = 1; i <= n; i ++)p[i] = i;

int res = 0, cnt = 0;
for(int i = 0; i < m; i ++){
int a= edge[i].a, b = edge[i].b, w = edge[i].w;
a = find(a), b = find(b);

if(a != b){
p[a] = b;
res += w;
cnt++;
}
}
if(cnt < n - 1)return INF;
return res;
}

int main(){
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i ++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge[i] = {a,b,c};
}
int t= kru();

if(t == INF)puts("impossible");
else printf("%d\n",t);

return 0;

}


#include<iostream>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
int n, m;
bool st[N];
int ans = 0;
int prim(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 1; j <= n; j ++){
if(!st[j]&&(t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
if(dist[t] == INF)return INF;
if(i)ans += dist[t];

for(int j = 1; j <= n; j ++){
dist[j] = min(dist[j], g[t][j]);
}
}
return ans;
}

int main(){
memset(g,0x3f,sizeof g);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++){
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}

int t = prim();

if(t == INF){
puts("impossible");
}
else printf("%d\n", t);
return 0;
}


#include<iostream>
#include<cstring>
using namespace std;

const int N = 210, M = 20010, INF = 1e9;
int g[N][N];
int n,m,k;

void floyd(){
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++)
g[i][j] = min(g[i][j], g[i][k]+ g[k][j]);
}
}
}

int main(){
scanf("%d%d%d",&n,&m,&k);
//memset(g, 0x3f, sizeof g);
for(int i = 0; i <= n; i ++){
for(int j = 0; j <= n; j ++){
if(i == j)g[i][j] = 0;
else g[i][j] = INF;
}
}
for(int i = 0; i < m; i ++){
int a, b, c;
scanf("%d%d%d",&a, &b, &c);
g[a][b] = min(g[a][b], c);
}
floyd();

while(k --){
int a,b;
scanf("%d%d",&a,&b);

int t = g[a][b];
if(t > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\n", t);
}

return 0;
}


RT

RT

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
int ans = N;
int n;
bool st[N];

e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u){
st[u] = true;

int size = 0, sum = 0;
for(int i = h[u]; i != -1; i = ne[i]){

int j = e[i];
if(st[j])continue;

int s = dfs(j);
size = max(size, s);
sum += s;
}

size = max(size, n - sum - 1);
ans = min(ans, size);

return sum + 1;
}

int main(){
scanf("%d",&n);
memset(h, -1, sizeof h);
for(int i = 0; i < n; i ++){
int a,b;
scanf("%d%d", &a, &b);
}
dfs(1);
printf("%d", ans);
}


#include<iostream>
using namespace std;

const int N = 2010, mod = 1e9 + 7;

int c[N][N];
int n;

void init(){
for(int i = 0; i < N; i ++)
for(int j = 0; j <= i; j++){
if(!j)c[i][j] = 1;
else{
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
}

int main(){
scanf("%d", &n);
init();
while(n --){
int a,b;
scanf("%d%d",&a, &b);
printf("%d\n", c[a][b]);
}

return 0;
}


#include<iostream>
using namespace std;
typedef long long LL;

int n;

int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a%b, y, x);
y -= a / b * x;
return d;
}

int main(){
scanf("%d", &n);

while(n--){
int a, b, m, x, y;
scanf("%d%d%d", &a, &b, &m);
int d = exgcd(a, m, x, y);
if(b % d)puts("impossible");
else{
printf("%d\n", (LL)x * (b / d) % m);
}
}

return 0;
}


#include<iostream>
using namespace std;

int n, a, b;

void exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return;
}

exgcd(b, a%b, y, x);
y -= a / b * x;
}

int main(){
scanf("%d",&n);

while(n --){
int x, y;
scanf("%d%d", &a, &b);
exgcd(a,b,x,y);
printf("%d %d\n",x, y);
}

return 0;
}


#include<iostream>
using namespace std;

typedef long long LL;

int pmi(int a, int b, int p){
int res = 1;
while(b){
if(b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a * a % p;
}

return res;
}

int main(){
int n ;
scanf("%d", & n);
while(n --){
int a,p;
scanf("%d%d",&a, &p);
if(a % p == 0)puts("impossible");
else printf("%d\n" , pmi(a, p - 2, p));
}

return 0;
}