Randomly sampling from list values and corresponding names

What I want to do is randomly sample from the list values (in this case cities) and create a variable from that sample. Also according to the city randomly picked, another variable (country) should contain the country that corresponds to the city of that observation.

list <- list(Spain = c("Barcelona", "Madrid"), Austria = c("Vienna", "Salzburg"), 
             France = c("Paris", "Lyon"), Italy = c("Milano", "Roma"))

cbind(Country = c("Italy", "Spain"), City = c("Roma", "Madrid"))