Java 8 Stream API to denormalize Map<A, Set<B>> to Map<B, A> without a Pair

I want to do something like the following, but I want to know if there is a more elegant way to do it without the Pair class. The Pair class no longer exists so I would have to create my own class, which is fine, but I'm just curious if there is a way to avoid it.

ordersByMerchant.entrySet().stream()
    .flatMap(merchantOrders -> {
          Merchant merchant = merchantOrders.getKey();
          Set<Order> orders = merchantOrders.getValue();
          return orders.stream()
              .map(order -> new Pair(order, merchant));
        }
    ).collect(toImmutableMap(
        Pair::getKey,
        Pair::getValue
    ));

Assuming Order instances are unique, then one could do this:

Map<Merchant,Set<Order>> ordersByMerchant = ... ;

Map<Order,Merchant> result =
    ordersByMerchant.entrySet().stream()
        .map(entry -> entry.getValue().stream()
                      .collect(toMap(order -> order, x -> entry.getKey())))
        .collect(HashMap::new, Map::putAll, Map::putAll);

It avoids an intermediate Pair class by transforming each {Merchant, Set<Order>} entry into an intermediate Map<Order,Merchant>. This results in a Stream<Map<Order,Merchant>>. The outer collector merges each of these intermediate maps into a single result map.

I admit this is kind of hard to follow. (It took a bit of effort write, too.) It would probably be better if the mapper were extracted into a separate method so that it could be commented.